Sorting Algorithm

Sorting Algorithm

• 1.
  Sorting Algorithms
• 2.
  GROUP MEMBERS Mohd. IftiarHossain – 152-15-5605 Md.Maruf Hasan – 152-15-5604 Md. Abu Shaik – 152-15-5612 Md. Abid Islam Riton – 152-15-5806 Trupti Agrawal
• 3.
  CONTENT INSRETION SORT SELECTION SORT BUBBLESORT MERGE SORT
• 4.
  • A sortingalgorithm is an algorithm that puts elements of a list in a certain order. • Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists Sorting Algorithms
• 5.
  Insertion sort • Cardplayers all know how to sort … – First card is already sorted – With all the rest, Scan back from the end until you find the first card larger than the new one, Move all the lower ones up one slot insert it p Q o 2 o 9 m A m K m 10 n J n 2 m 2 o 9 ‚ ƒ „
• 6.
  To insert 12,we need to make room for it by moving first 36 and then 24. Insertion Sort 6 10 24 12 36
• 7.
  6 10 24 InsertionSort 36 12
• 8.
  Insertion Sort 6 1024 36 12
• 9.
  Insertion Sort 5 24 6 1 3 input array left sub-array right sub-array at each iteration, the array is divided in two sub-arrays: sorted unsorted
• 10.
  Insertion Sort
• 11.
  Insertion Sort -Summary • Advantages – Good running time for “almost sorted” arrays Θ(n) • Disadvantages – Θ(n2 ) running time in worst and average case – ≈ n2 /2 comparisons and exchanges
• 12.
  Selection Sort • Idea: –Find the smallest element in the array – Exchange it with the element in the first position – Find the second smallest element and exchange it with the element in the second position – Continue until the array is sorted • Disadvantage: – Running time depends only slightly on the amount of order in the file
• 13.
  Example-Selection Sort 1329648 8329641 8349621 8649321 8964321 8694321 9864321 9864321
• 14.
  Bubble Sort • Idea: –Repeatedly pass through the array – Swaps adjacent elements that are out of order • Easier to implement, but slower than Insertion sort 1 2 3 n i 1329648 j
• 15.
  Example - BubbleSort
• 16.
  Bubble Sort Alg.: BUBBLESORT(A) fori ← 1 to length[A] do for j ← length[A] downto i + 1 do if A[j] < A[j -1] then exchange A[j] ↔ A[j-1] 1329648 i = 1 j i
• 17.
  Merge Sort Approach •Divide – Divide the n-element sequence to be sorted into two subsequences of n/2 elements each • Conquer – Sort the subsequences recursively using merge sort – When the size of the sequences is 1 there is nothing more to do • Combine – Merge the two sorted subsequences
• 20.
  DISCUSSION and Conclusion