Sorting Techniques

Sorting Techniques

1. Decrease-and-conquer technique

   • It is based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance
     • The three major variations of this technique are: 1- decrease by a constant, 2- decrease by a constant factor and 3- variable size decrease
       • In the decrease-by-a-constant variation, the size of an instance is reduced by the same constant on each iteration of the algorithm
       • The decrease-by-a-constant-factor technique suggests reducing a problem instance by the same constant factor on each iteration of the algorithm
       • in the variable-size-decrease variety, the size-reduction pattern varies from one iteration of an algorithm to another.
   • Insertion Sort
     • Though insertion sort is based on a recursive idea, it is more efficient to implement this algorithm bottom up
     • Is done by scanning the sorted subarray from right to left until the first element smaller than or equal to A[n − 1] is encountered to insert A[n − 1] right after that element

2. Divide-and-conquer

   • These algorithms work according to the following general plan: 1. A problem is divided into several subproblems of the same type, 2. The subproblems are solved, 3. If necessary, the solutions to the subproblems are combined to get a solution to the original problem.
     • the time spent on executing this is usually (but not always) significantly smaller than solving a problem by a different method.
   • Mergesort
     • It sorts a given array A[0..n − 1] by dividing it into two halves A[0..⌊n/2⌋ − 1] and A[⌊n/2⌋..n − 1], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one.
       • There are two main ideas leading to several variations of mergesort
         • the algorithm can be implemented bottom up by merging pairs of the array’s elements, then merging the sorted pairs, and so on
         • we can divide a list to be sorted in more than two parts, sort each recursively, and then merge them together
     • The number of key comparisons made by mergesort in the worst case comes very close to the theoretical minimum2 that any general comparison-based sorting algorithm can have

3. Brute-force approach

   • Selection Sort
     • It works by scanning the entire given list to find its smallest element and exchange it with the first element, doing this to all n-1 elements
       • After n − 1 passes, the list is sorted
   • Buble Sort
     • It works by comparing 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 on the list
     • different of selection sort, the number of key swaps depends on the input

Bilder und Dateien der Mindmap