Sorting:Quick Sort
Sorting:
Sorting is the process of categorising and organising information in a logical order. Components can be sorted in ascending or descending order based on a linear relationship between the data items. Names, numbers, and records can all be sorted. For example, because the names in the phone book have been arranged into alphabetical order, it is quite easy to seek up a friend’s phone number from a telephone dictionary. This case shows one of the primary reasons why sorting big amounts of data is beneficial. Sorting, in other words, makes searches much more efficient. If we opened a phone book and discovered that the names were not in any logical sequence, we would be concerned.
The key benefit of sorting is time complexity, which is the most significant factor to consider when solving a problem. It is not enough to be able to solve a problem; you must also be able to do it in the shortest amount of time feasible. Sorting may sometimes solve problems quickly and easily, saving you from every Coder’s Nightmare, such as TLE (Time Limit Exceeded).
There are some algorithms which can be used to sort a given data, Quick sort, Merge sort, Radix sort, Bucket sort, Heap sort are some of the examples.
Quick Sort Algorithm:
Quicksort is an algorithm for sorting data in real time. In 1959, it was invented by Tony Hoare, a British computer scientist. It can be somewhat quicker than merge sort and two or three times faster than heapsort when properly done.
Quicksort is based on the divide-and-conquer strategy. It operates by picking a ‘pivot’ element from the array and separating the other elements into two sub-arrays based on whether they are greater or less than the pivot. As a result, it’s also known as partition-exchange sort. The sub-arrays are then recursively sorted. This can be done in-place, with only a little amount of additional RAM required for sorting.
It is a comparison sort, which means it can sort objects of any type that have a “less-than” relation (technically, a total order) declared for them.
Quicksort is not a stable sort, which implies that in efficient implementations, the relative order of equal sort items is lost.
Let’s take an array A = [10,15,1,2,6,12,5,7]. Let 7 be the Pivot Element. The array is now split into two sub-arrays, with all elements less than pivot going to the left sub-array and all elements greater than pivot going to the right sub-array.
Now we get two more Arrays i.e., B = [1,2,6,5] and C = [12,15,10]. 5 and 10 are taken as Pivot Element for B and C arrays respectively. Now, again two more arrays are created and elements less than pivot going to the left sub-array and all elements greater than pivot going to the right sub-array. Finally, a sorted array is received.
Time Complexities:
· Worst-Case — The worst-case scenario is when the partitioning algorithm always chooses the largest or smallest element as the pivot. When the array is already sorted in increasing or decreasing order. (O(n²))
· Best Case — When the partitioning algorithm always chooses the middle element as pivot. (O(nLogn))
· Average Case — Consider the instance where a partition places O(n/9) elements in one set and O(9n/10) elements in the other set to get a notion of the typical case. ((nLogn))
