Quick Sort, Insertion Sort, Merge Sort in Data Structure

Quick Sort

What is Quick Sort-?

The quick sort algorithm items to separates the list of elements into two parts and then sort each part recursively. It use divide an conquer method. In this method the patrician of list is performed based on the element called pivot element.

                The list is divided into two partician, such that all the elements to the left pivot are smaller then the pivot and all element of right of pivot are greater then or equal to pivot.

Algorithm of Quick sort in Data Structure

Step 1:- Begin

Step 2:- Select the start element of array as pivot element

Step 3:- Scan and find smallest element from the right side of array

Step 4:- Interchange both elements

Step 5:- Scan and find the biggest element from the left side of the array

Step 6:- Repeat the above process until all the elements of left side are smaller and the right side elements are greater than pivot element

Step 7:- Now, we have two sub-list are available, apply same process on each sub-list until all the elements of array are not sorted

Step 8:- Exit

What is Insertion Sort in Data Structure-?

Insertion Sort arrange N elements of array by inserting particular item in a particular place such a way that the item are in sorted order.

Algorithm of Insertion Sort in Data Structure

Step 1:- Begin

Step 2:- Input a[5]={7, 6, 3, 4, 1}

Step 3:- Set i ⬅ 1

Step 4:- Repeat step 5 to 9, while (i<5)

Step 5:- Set j ⬅ i

Step 6:- Repeat step 7 and 8 while j>=1

Step 7:- if a[j-1]>a[j], then

                Set temp ⬅ a[j-1]

                a[j-1] ⬅ a[j]

                a[j] ⬅ temp

Step 8:- j ⬅ j-1

Step 9:- i ⬅ i+1

Step 10:- print a[5]

Step 11:- End

What is Merge Sort in Data Structure-?

Merge Sort is a sort algorithm that splits the items of array to be sorted into two groups, recursively sort each group and merge them into a final sorted sequence

Algorithm of Merge Sort in Data Structure

Step 1:- Begin

Step 2:- Divides all the items of array into two items pairs. If single item remains make a single group

Step 3:- Sort each of the pair

Step 4:- Merge two pairs into single pair

Step 5:- Sort the merge pair

Step 6:- Repeat the above steps until the all elements of array are not sorted

Step 7:- Exit

Difference Between Array and Linked List

S.no	Array	Linked List
1	Array is the collection of homogeneous (Similar) data type	Linked list is a collection of nodes (data and address)
2	Array elements are sorted in continuous memory location	Linked list elements can be stored anywhere in the memory
3	Array works with static data structure	Linked list works with dynamic data structure
4	Array elements are independent to each other	Linked list elements are dependent to each other
5	Array takes more time	Linked list takes less time
	Example:- Insertion, Deletion etc...,	Example:- Insertion, Deletion etc...,