Sorting is the technique of organising elements in an array in ascending or descending order.
Example of Sorting Algorithm
In the above example, we have an array
int A[6] = {8,1,3,2,7,4}
Now the sorted or organised array will look like:
Int A[6] = {1,2,3,4,7,8}
Here, we have sorted the array in ascending order.
This operation can be completed using a variety of sorting algorithms. And depending on the situation, we can use any algorithm.
Types of Sorting Algorithms
Bubble Sort
Bubble sort is one of the most simple sorting algorithms that continually steps through the index, compares adjacent components and swaps them if they are placed in the incorrect order.
Selection Sort
Selection sort finds the smallest component in the list and puts it in the first position on the list, then it searches for the second last element in the array and puts it in the second position. This procedure continues until all the components are transferred to their accurate placement.
Insertion Sort
Insertion sorting is an uncomplicated sorting technique that inserts each component of the array to its appropriate position.
Merge Sort
Merge sort prefers the divide and conquer strategy to organise the elements. It is one of the most efficient sorting algorithms. It breaks the provided array into two parts, then sorts them and merges them.
Quicksort
Quicksort is one of the most optimised sorting techniques that follow the divide and conquer strategy.
Counting Sort
Counting sort is a sorting algorithm that sorts an array’s elements by estimating the appearance of unique elements in the array.
Radix Sort
In the Radix sort algorithm, the sorting is performed based on a dictionary or alphabetical order. It is the linear sorting algorithm that we mostly prefered for integers.
Bucket Sort
In the bucket sort algorithm, the buckets are sorted separately by utilising distinct sorting algorithms.
Heap Sort
It is a popular comparison-based sorting approach based on Binary Heap data structure. It is very much similar to the selection sort algorithm where we first encounter the lowest element and put the lowest element at the front.
Shell Sort
Shell sort is an extension of insertion sort that compares elements separated by multiple locations to solve the disadvantages of insertion sort.
Practice Problems
Q1. Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?
I. Quicksort runs in Θ(n2) time
II. Bubble sort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time
(A) I and II only
(B) I and III only
(C) II and IV only
(D) I and IV only
Q2. Assume that a mergesort algorithm, in the worst case, takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?
(A) 256
(B) 512
(C) 1024
(D) 2048
Q3. The number of elements that can be sorted in Θ(log n) time using heap sort is _________.
(A) Θ(1)
(B) Θ(logn−−−−√)
(C) Θ(lognlog logn)
(D) Θ(logn)
Q4. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is _________.
(A) T(n) = 2T(n − 2) + 2
(B) T(n) = 2T(n − 1) + n
(C) T(n) = 2T(n/2) + 1
(D) T(n) = 2T(n − 1) + 1
Q5. The running time of an algorithm is represented by the following recurrence relation:
T(n)={nT(n3)+cnn≤3otherwise
Which one of the following represents the time complexity of the algorithm?
(A) Θ(n)
(B) Θ(nlogn)
(C) Θ(n2)
(D) Θ(n2logn)
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
Comments