A Comparative Study on Sorting Algorithms
“In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order.”
Need of sorting algorithms
A sorting a list of items can take a long time, especially if it is a large list. A computer program can be created to do this, making sorting a list of data much easier. Sorting algorithm is a method for reorganizing a large number of items into a specific order, such as alphabetical, highest-to-lowest value or shortest-to-longest distance. Sorting algorithms take lists of items as input data, perform specific operations on those lists and deliver ordered arrays as output.
Sorting Algorithms
Sorting is a process of rearrangement a list of elements to the correct order since handling the elements in a certain order more efficient than handling randomize elements. Sorting and searching are among the most common programming processes, as an example take database applications if you want to maintain the information and ease of retrieval you must keep information in a sensible order, for example, alphabetical order, ascending/descending order and order according to names, ids, years, departments, etc.
The sorting techniques can be divided into two categories:
Internal Sort : In internal sorting, all the data to sort is stored in memory at all times while sorting is in progress. e.g : bubble sort, quick sort, insertion sort, selection sort , etc.
External Sort : In external sorting data is stored outside memory (like on disk) and only loaded into memory in small chunks. External sorting is usually applied in cases when data can’t fit into memory entirely. e.g : merge sort , heap sort , etc.
Bubble Sort
The bubble sort works on the basis for given lists by swapping adjacent item or data in order, until the entire lists of item or data are obtained in a sequence based upon their key values. This technique is popular and easy for execution of data in which it does not require extra storage space.
This takes the following steps as shown below:
Step 1: Consider the set of elements which can be of any data for the given lists.
Step 2: Swap first two data for the given lists adjacently using one by one pairs.
Step 3: Repeat the process for all the items or data in the given list.
Step 4: Return result for the same.
Advantages:
◾ It is one of the popular and easily implemented algorithms.
◾ Without using the extra storage, the items can be swapped easily.
◾ Requires minimum space for given lists.
Disadvantages:
◾ Requirement of N-squared number steps for sorting items.
◾ Does not deal with large number of items for the given lists.
◾ Cannot be used for real time applications.
Selection Sort
One of the simplest techniques used is the selection sort which works for the given lists of item or data each time by selecting one item at a time and orders along with placing it in a correct position in sequence. This does not require extra storage space to hold the lists. For selecting the item randomly this technique is helpful.
The following steps are used for processing the elements in given lists of items
Step 1: First finds the smallest element for the given lists of item or data.
Step 2: Replaces that item or data in the first position.
Step 3: Next, again finds the smallest element among the lists.
Step 4: Get replaced in second position.
Step 5: Same procedure is followed unless the elements are sorted.
Step 6: Returns result.
Advantages:
◾ Before sorting the given lists, the ordering of data can be initialized.
◾ This works even for the smaller lists of items or data.
◾ Need no extra storage for the original lists of items.
Disadvantages:
◾ For the large set of items or data this sorting results in poor efficiency.
◾ Requires an N-squared number steps for sorting items for the given lists.
◾ Compared to selection sort, the quick sort is most efficient.
Quick Sort
Quick sort as the name suggests helps in sorting list of items very quickly with less space and is based upon the Divide and Conquer principle also known as a Partition Exchange sort. This type of sorting is known as one of the best sorting algorithms as it has efficiency and can handle complex and vast lists of item without using extra storage in it.
It takes the following steps for processing of an item or data for the given list:
Step 1: Pick the element from the given list and use as a pivot.
Step 2: Partition these elements into two sub-lists.
◾ Elements less than pivot.
◾ Elements greater than pivot.
Step 3: Quick sort two sub-lists.
Step 4: Repeat the process until the entire lists of item are sorted.
Step 5: Return result
Advantages:
◾ This is one of the best sorting algorithms.
◾ It can handle large items for the given lists.
◾ Does not require extra storage.
Disadvantages:
◾ The worst-case performance is same as bubble, selection and insertion sort.
◾ In case the given lists are already sorted, then bubble sort is more efficient compared to quick sort.
◾ For sorting the integers of given items, radix sort plays an important role as compared to quick sort.
Insertion Sort
Insertion sort is an in-place sorting algorithm which is based on comparison. Here, a small part of the list is maintained which is already sorted. For instance, the lower part of an array is taken which is sorted. A data item that is to be inserted in this sorted sub-list must find its appropriate place and then it is to be inserted. Hence it is known as insertion sort. The given array is searched linearly and unsorted data items are moved and inserted into the sorted sub-list in the array.
It takes the following steps for processing of an item or data for the given list:
Step 1: If the first element is already sorted, Return 1;
Step 2: Take the next element
Step 3: Compare the element with all other elements in sorted sub-list
Step 4: Move all the elements in the sorted sub-list which is bigger than the Value to be sorted
Step 5: Insert the value
Step 6: Repeat until list is sorted
Advantages:
◾ Simple implementation
◾ Efficient for small data sets
◾ It is stable
Disadvantages:
◾ Less efficient for the list containing more elements
◾ It needs large number of element shifts
Merge Sort
Merge sort is a sorting technique which is based on the divide and conquers technique. Though the worst-case time complexity being Ο(n log n), it is one of the most respected algorithms. It first divides the given array into two equal parts and then joins them in a sorted manner.
It takes the following steps for processing of an item or data for the given list:
Step 1: If the first element is already sorted, return 1.
Step 2: The list is divided recursively into two equal parts until it cannot be divided.
Step 3: Combine the smaller list of data items into the new list which has sorted elements.
Advantages:
◾ Merge sort can be useful to files of any size.
◾ It is fast and stable
Disadvantages:
◾ Merge Sort takes more space when compared to other sorts.
◾ Merge sort is less efficient than other sort
Heap Sort
It is the best in-place sorting algorithm with no quadratic worst-case situations. This algorithm is divided into two basic parts: Creating a Heap of the unsorted list and Then a sorted array is generated by continuously removing the greatest\smallest data item from the heap, and placing the data item into the array. The heap is rebuilt after each removal
It takes the following steps for processing of an item or data for the given list:
Step 1: Build a max heap from the input data.
Step 2: At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
Step 3: Repeat above steps while size of heap is greater than 1.
Advantages:
◾ Because of its efficiency, this algorithm is widely used.
◾ As it is an in-place sorting algorithm its memory usage is nominal.
Disadvantages:
◾ More space is required for sorting
◾ Quick sort is more efficient when compared to Heap in most of cases
Performance in Average Case Between Sorting Algorithms
Many different sorting algorithms have been developed and improved to make sorting fast. As a measure of performance mainly the average number of operations or the average execution times of these algorithms have been investigated and compared. There is no one sorting method that is best for every situation. Some of the factors to be considered in choosing a sorting algorithm include the size of the list to be sorted, the programming effort, the number of words of main memory available, the size of disk or tape units, the extent to which the list is already ordered, and the distribution of values.
Implementation of Selection sort, Quick sort, Insertion sort , Merge sort and Bubble sort algorithms using C++ programming language is done and execution time of all programs is measured with the same input data using the same computer. The built-in function (clock ()) in C++ is used to get the elapsed time of the implementing algorithms, execution time of a program is measured in milliseconds. The performances conventional sort algorithms are comparatively tested under average cases by using random test data from size 10000 to 30000.
Complexity Comparison between Typical sorting algorithms
The comparison of complexity between sorting algorithms are listed in table,
Conclusion
Comparative study of sorting algorithms like selection sort, Insertion sort, merge sort, quick sort, heap sort and bubble sort is done. Performance of these algorithms is analyzed by taking same number of elements/inputs (10000,20000, 30000). For small number of inputs, the performance for the six techniques is almost nearest, but for the large number of inputs, Quick sort is the fastest and the selection sort the slowest. In average and worst case, the time complexity with selection, Insertion and bubble sort is nearly same. This research is initial step for future work, in the future we will improve our research on various such algorithms to optimize software’s in searching method and retrieve data.
References
◾ Adesina, Opeyemi. (2013). A Comparative Study of Sorting Algorithms. African Journal of Computing & ICT. 6. 199–206.
◾ Ms Roopa K , Ms. Reshma J. (2018). A Comparative Study of Sorting and Searching Algorithms. International Research Journal of Engineering and Technology.
◾ Ibrahim Mahmoud AlTurani , etal.(2013). Review on Sorting Algorithms A Comparative Study. International Journal of Computer Science and Security (IJCSS), Volume (7) : Issue (3) : 2013
◾ B Subbarayudu , etal. (2017). Comparative Analysis on Sorting and Searching Algorithms. International Journal of Civil Engineering and Technology (IJCIET) Volume 8, Issue 8, August 2017.
Contributors
◾ Chetan Lohkare
◾ Harsh Kulkarni
◾ Prathamesh Kulkarni
◾ Vishal Khandate
