# When is QuickSort impractical?

## Algorithms and data structures

Algorithms and data structures Dipl. Inform. Andreas Wilkens

Sorting algorithms In order to bring the data records of a database into an ascending or descending order, a number of different methods have been developed. The most important are shown below.

Sorting algorithms Selection Sort Bubble Sort Insertion Sort Quick Sort

Selection Sort Sort by direct selection. Procedure Find the smallest element in the database and swap it with the element at position 1. Find the second-smallest element and swap it with position 2. Find the third-smallest element and swap it with position 3. etc.

Sorting algorithms Selection Sort Bubble Sort Insertion Sort Quick Sort

Bubble Sort Go through the data to be sorted again and again and look at neighboring elements. If a larger date precedes a smaller one, swap the two with one another. This is repeated until it was no longer necessary to swap in one run.

Sorting algorithms Selection Sort Bubble Sort Insertion Sort Quick Sort

Insertion Sort Insertion sort works like sorting playing cards from a pile into your hand. You simply take card by card from the stack and sort them by comparing the card value with all cards already in your hand (from right to left).

Sorting algorithms Selection Sort Bubble Sort Insertion Sort Quick Sort

Quick Sort One of the most common sorting algorithms is Quick Sort. The actual idea comes from C.A.R. in 1960. Hoare.

Quick Sort The idea for Quick Sort came from a project for mechanical translation Russian -> English words saved on magnetic tape, faster access -> sorting Hoare keeps autmat. Translation for impractical: By-product Quick Sort Quick Sort is a "waste product"

Quick Sort Quick Sort works on the "divide and conquer" principle. A field is divided into two parts, which are then sorted independently of each other.

Quick Sort An element T is selected, which is placed in the correct position in the sorted order by the partition () function. At the same time, partition () ensures that only smaller (identical) elements are to the left of T and only larger (identical) elements to the right. (These areas are not yet sorted!) The procedure is then applied to the left and right subfields.

Quick Sort

Quick Sort The difficulty now lies in breaking up the field.  Function partition (…) The field must be rearranged so that the following conditions are met: The element array [p] is at the correct index p in the field. All elements array  to array [p-1] are less than or equal to array [p]. All elements array [p + 1] through array [n-1] are greater than or equal to array [p].

Quick Sort At the beginning you choose two indices i = l + 1 and j = r and the first element in the field as comparison value key = array [l]. In a loop, increase i until the array element array [i]> key. This field element belongs in the right half of the field. All elements of the right half should be larger than key. In a loop, decrease j until the array element array [j] = j terminate the loop. (Go to 7.) Swap the elements array [i] and array [j]. Repeat everything from point 2. Finally, swap the first element in the field (key) with array [j]. This means that all of the above conditions are met.