Scribd
Upload
119 views10 pages

Sorting Algorithms Guide

The document discusses different sorting algorithms. It explains that sorting means arranging elements in an array in a relevant order like ascending or descending. There are two types of sorting: internal sorting which deals with sorting data in memory, and external sorting which deals with sorting large datasets stored in files. Some common sorting algorithms discussed include bubble sort, insertion sort, selection sort, merge sort, quick sort, and heap sort. The performance of sorting algorithms is analyzed based on factors like number of comparisons and data movements.

Uploaded by

Debasish Vishal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
119 views10 pages

Sorting Algorithms Guide

The document discusses different sorting algorithms. It explains that sorting means arranging elements in an array in a relevant order like ascending or descending. There are two types of sorting: internal sorting which deals with sorting data in memory, and external sorting which deals with sorting large datasets stored in files. Some common sorting algorithms discussed include bubble sort, insertion sort, selection sort, merge sort, quick sort, and heap sort. The performance of sorting algorithms is analyzed based on factors like number of comparisons and data movements.

Uploaded by

Debasish Vishal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 10

Data Structure

Sorting Algorithms

Prepared by
Dalton Meitei Thounaojam
Sorting

 Sorting means arranging the elements of an array


so that they are placed in some relevant order
which may be either ascending or descending.
 There are two types of sorting:
 Internal sorting: which deals with sorting the data
stored in the computer’s memory.
 External sorting: which deals with sorting the data
stored in files. External sorting is applied when there
is voluminous data that cannot be stored in the
memory.
Sorting

 for analysing the performance of different sorting


algorithms, the practical considerations would be
the following:
 Number of sort key comparisons that will be performed
 Number of times the records in the list will be moved
 Best case performance
 Worst case performance
 Average case performance
 Stability of the sorting algorithm where stability means
that equivalent elements or records retain their relative
positions even after sorting is done
Sorting

 Different types of sorting algorithms:


 Bubble Sort
 Insertion Sort
 Selection Sort
 Merge Sort
 Quick Sort
 Radix Sort
 Heap Sort
 Shell Sort
 Tree Sort
Bubble Sort

Step 1: Repeat Step 2 For I = 0 to N-1


Step 2: Repeat For J = 0 to N – I – 1
Step 3: IF A[J] > A[J + 1]
SWAP A[J] and A[J+1]
[END OF IF]
[END OF INNER LOOP]
[END OF OUTER LOOP]
Step 4: EXIT

Note: Complexity of bubble sort is O(n2).


Bubble Sort

 First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), no swap since 5 < 8
 Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), no swap since 1 < 4
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), no swap since 4 < 5
 Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), no swap since 1 < 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), no swap since 2 < 4
 Fourth Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ), no swap since 1 < 2
Insertion Sort

Step 1: Repeat Steps 2 to 5 for I = 1 to N – 1


Step 2: SET TEMP = ARR[I]
Step 3: SET J = I - 1
Step 4: Repeat while TEMP <= ARR[J]
SET ARR[J + 1] = ARR[J]
SET J = J - 1
[END OF INNER LOOP]
Step 5: SET ARR[J + 1] = TEMP
[END OF LOOP]
Step 6: EXIT

Note: Complexity of insertion sort is O(n2).


Insertion Sort

39, 9, 45, 63, 18

39

Pass 1 9 39

Pass 2 9 39 45

Pass 3 9 39 45 63

Pass 4 9 18 39 45 63
Selection Sort

Step 1: Repeat Steps 2 and 3 for K = 1 to N-1


Step 2: [INITIALIZE] SET SMALL = ARR[K]
Step 3: [INITIALIZE] SET POS = K
Step 4: Repeat for J = K+1 to N
IF SMALL > ARR[J]
SET SMALL = ARR[J]
SET POS = J
[END OF IF]
[END OF LOOP]
Step 5: SWAP A[K] with ARR[POS]
[END OF LOOP]
Step 6: EXIT
Note: Complexity of selection sort is O(n2).
Thank you

You might also like