COMPARISON SORTING ALGORITHMS

COMPARISON SORTING ALGORITHMS

1. Algorithms used to sort data according to a condition (i.e. increasing/decreasing) - These algorithms 'compare' values and make the appropriate swaps according to the resutlt

2. SORTING ALGORITHMS

   • NON-COMPARISON ALGORITHMS
     • Counting Sort
     • Radix Sort
     • Bucket Sort

3. Bubble Sort

   • WHILE LOOP: checks whether any swap was made during the last pass through the array
   • FOR LOOP: makes a pass through the array and performs any required swap
     • At the end of 1 entire execution of this loop, this next highest value is in its right position
   • TIME COMPLEXITY: BEST CASE: θ(N) WORST CASE:θ(N^2)

4. Insertion Sort

   • TIME COMPLEXITY: BEST CASE: θ(N) WORST CASE:θ(N^2)
   • For Loop: selects the next element to be inserted in the sorted part of the array
     • While Loop: makes space to insert the elemet

5. Selection Sort

   • TIME COMPLEXITY: BEST CASE: θ(N^2) WORST CASE:θ(N^2)
   • For Loop: determines the position where the next min # is stored
     • position_min returns the position of the min value between positions a and b in array A

6. Merge Sort

   • TIME COMPLEXITY: BEST CASE: θ(NlogN) WORST CASE:θ(NlogN)
   • Breaks apart iinto elements, merges back together

7. Quick Sort

   • TIME COMPLEXITY: BEST CASE: θ(NlogN) WORST CASE:θ(N^2)
   • Partition: selects the pivot, moves all #s lower than pivot to left, moves the pivot to its final position
     • RECURSIVE CALL: LEFT HALF
       • RECURSIVE CALL: RIGHT HALF

Bilder und Dateien der Mindmap