What is Sorting?
Sorting is a fundamental mathematical operation that involves arranging or rearranging a collection of items in a specific order. The primary goal of sorting is to impose a linear order on a list or array of elements based on certain criteria. This ordered arrangement facilitates efficient searching, retrieval, and manipulation of data.
Types of sorting
- Internal sorting: Internal sorting refers to sorting records or elements within the main memory of a computer system. This means the entire dataset, including all the records to be sorted, resides in the RAM or primary storage.
- External sorting: External sorting involves sorting records that exceed the capacity of the main memory. In this scenario, some records are stored in external memory, such as disk drives, while portions of the data are brought into the main memory for sorting.
- Exchange Sort:
Exchange sort, also known as swapping sort, involves comparing pairs of elements in a list and swapping them if they are in the wrong order. The process continues until the entire list is sorted. Prominent examples of exchange sort algorithms include Bubble Sort and Quick Sort.
- Selection Sort:
Selection sorting involves dividing the list into a sorted and an unsorted region. The algorithm iteratively chooses the smallest (or largest) element from the portion of the collection that is yet to be sorted, relocating it to its appropriate position within the already sorted portion. Selection Sort and Heap Sort are examples of selection sort algorithms.
- Insertion Sort:
Insertion sort builds the sorted list one element at a time by considering each element and inserting it into its correct position relative to the already sorted elements. Insertion Sort and Merge Sort are examples of insertion sort algorithms.
In Bubble Sort, the algorithm traverses the list in successive iterations, inspecting neighboring elements and exchanging them if their order is incorrect. This process continues until a pass through the list occurs without any further swaps, indicating the attainment of a sorted arrangement.
Algorithm:Compare the first two elements. If they are in the wrong order, swap them.Move to the next pair of elements and repeat the comparison and swapping.Continue this process for the entire list in multiple passes until no more swaps are required.
This algorithm is good for a small number of elements, usually less than 100. Conversely, it is not an efficient algorithm for large datasets. The Time complexity is
Output of code:
It sorts a list of records by inserting a new element into an existing sorted list. The array is virtually divided into sorted and unsorted lists. An initial list with only one item is considered a sorted list.
- The algorithm iterates through the array, comparing each element to its predecessors.
- If the current element is smaller than its predecessor, it is compared to elements before it and larger elements are shifted to the right to make space for the current key.
- This process continues until the key is in its correct position in the sorted portion of the array.
- The algorithm repeats this process for each element, gradually building the sorted array.
Original Array: 87 65 25 12 22 11 90
Sorted Array: 11 12 22 25 65 87 90
No of comparisons:
- Best case: n – 1
- Worst case: n2/2 + O(n)
- Average case: n2/4 + O (n)
No of assignments (movements)
- Best case: 2*(n-1)
- Worst case: n^2/2+O(n)
- Average Case : n^2/4 + O(n)
Hence running time of insertion sort is O(n^2) in the worst and average case and O(n) in the best case, and the space requirement is O(1)
- It is an excellent method whenever a list is nearly in the correct order, and few items are removed from their correct locations.
- Since there is no swapping, it is twice as faster as bubble sort.
- It makes a large amount of shifting of sorted elements when inserting later elements.
The selection sort algorithm sorts a list by selecting successive elements in order and placing them into their proper sorted positions.
- The entire list is scanned sequentially for the first position in the sorted list. You search the whole list, find the lowest value, and place it in the first position.
- The entire list is scanned sequentially for the second position in the sorted list. You search the whole list, find the lowest value, and place it in the second position.
- The whole process is repeated until the entire list is sorted.
No of comparisons:
- Best, average and worst case: n(n – 1)/2
No of assignments (movements)
- Best, average and worst case: 3(n – 1)
total: n – 1 swaps
If we include a test to prevent interchanging an element with itself, the number of interchanges in the best case would be O.
Hence running time of the selection sort is O(n^2), and additional space requirements are O(1).
- It is the best algorithm for data movement.
- An element that is in its correct final position will never be moved.
- In the case of several comparisons, it pays no attention to the original ordering of the list. For a list that is nearly correct to begin with, the selection sort is slower than the insertion sort.
Thank you for reading this article. Please consider subscribing if you loved it.