# 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={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
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...,

1. 2. 