Ion Of All Sorting

sorting

TECHNIQUES By… Sukanta behera Reg. No. 07SBSCA048

Topic overview: 









NOTES ON SORTING. SELECTION SORT ALGORITHM AND EXAMPLE. BUBBLE SORT ALGORITHM AND EXAMPLE. MERGE SORT ALGORITHM AND EXAMPLE. QUICK SORT ALGORITHM AND EXAMPLE.

SORTING: 

The sorting technique asks us to rearrange the given items of a given list in ascending order.



As a practical manner, we usually need to sort lists of numbers, characters from an alphabet, character strings, and most important records in an institutions, companies etc.



For example, we can choose to sort student

Selection sort: 

Selection sort and Bubble sorting techniques are coming under Brute Force method, which is a straightforward approach to solving a problem’s statement and definitions of the concepts involved. ALGORITHM SelectionSort(A[o..n-1]) //The algorithm sorts a given array by selection sort //Input: An array A[0..n-1] of orderable elements //Output: Array A[0..n-1] sorted in ascending order for i=0 to n-2 do min=i for j=i+1 to n-1 do if A[j] < A[min], min=j swap A[i] and A[min]

Bubble sort: 

Bubble sort is comes under Brute Force method. The sorting problem is to compare adjacent elements of the list and exchange them if they are out of order . By doing it repeatedly, we end up “bubbling up” the largest element to the last position of the list and vice versa. ALGORITHM

BubbleSort(A[0..n-1])

//The algorithm sorts array A[0..n-1] by bubblesort //Input: An array A[0..n-1] of orderable elements //Output: Array A[0..n-1] sorted in ascending order for i=0 to n-2 do for j=0 to n-2-I do

Merge sort: 

Merge sort is a perfect example of a successful application of the Divide and Conquer method. It sorts a given array A[0..n1] by dividing it into two halves A[0..[n/2]-1] and A[[n/2]…n1]. Sorting each of them recursively and then merging the two smaller sorted arrays into a single sorted one.

ALGORITHM

Mergesort(A[0..n - 1])

//Sorts array A[0..n - 1] by recursive mergesort //Input: An array A[0..n - 1] of orderable elements // Output: Array A[0..n - 1] sorted in decreasing order if n > 1 copy A[0..[n/2] - 1] to B[0…[n/2] - 1] copy A[[n/2]..n - 1] to C[0…[n/2] - 1] Mergesort (B[0..[n/2] - 1]) Mergesort (C[0..[n/2] - 1]) Merge (B, C, A)

89

45

68

90 12

29

89 45 68 90 89 45 8 9

29 34

6 8

45 89

9 0

2 9

68 90

17

17 12 3 4

1 7

29 34

29

34 45 90

68

1 2

12 17

12 17 29 34

45 68 89 90 12

17

29 34 17 12

68 90 4 5

34

89

Quick Sort: 

Quick sort is another important sorting algorithm that is based on the Divide and Conquer method. It divides the input elements according to their value. Specifically, it rearranges elements of a given array A[0..n – 1] to achieve its partition.

ALGORITHM

Quicksort(A[l…r])

//Sorts a subarray by quicksort //Input: A subarray A[l…r] of A[0..n – 1], defined by its left & right indices //Output: The subarray A[l…r] sorted in nondecreasing order if l < r

ALGORITHM Partition(A[l…r]) //Partitions a subarray by using its first element as a pivot //Input: A subarray A[l..r] of A[o…n – 1], defined by its left and right // indices l and r (l < r) //Output: A partition of A[l..r], with the split position returned as this // function’s values p = A[l] i = l; j = r + 1 repeat repeat i = i + 1 until A[i] >= p repeat j = j - 1 until A[j] <= p Swap(A[i], A[j]) until i >= j swap(A[i], A[j]) //undo last swap when i >= j swap(A[l],A[j])

0

1 3

5

i3

2 4

3 5

4 6

5

6

7

0

1

2

2

3

7

1

9

8

2

4

j7

1 1

4 5

3

1

i9

8

2

j4

7

5

3

1

i4

8

2

j9

7

3

3

1

4

i8

j2

9

7

i3

3

1

4

j2

i8

9

7

ij4 5 j4 5

4

Insertion sort: 

Insertion sort comes under Decrease and Conquer method. In this method, we consider an application of the decrease-by-one technique to sorting an array A[0… n – 1]. ALGORITHM Insertionsort(A[0…n – 1]) //Sorts a given array by insertion sort // Input: An array A[0…n – 1] of n orderable elements // Output: Array A[0…n – 1] sorted in nondecreasing order for i =1 to n – 1 do v = A[i] j=i–1 while j >= 0 and A[j ] > v do A[j + 1] = A[j] j=j–1 A[j + 1] = v