Quick Sort (Part- 4)

REFERENCE : PANIMALAR ENGINEERING COLLEGE NOTES
Quick Sort:
Quick sort is one of the most efficient internal sorting technique. It possess a very good average behavior among all the sorting techniques. It is also called as partitioning sort which uses divide and conquer techniques.
                The quick sort works by partitioning the array A[1], A[2]. . . A[N] by picking some key value in the array as a pivot element.Pivot element is used to rearrange the elements in a array. Pivot element can be the first element of an array and the rest of the elements are moved so that elements on left side of the pivot are lesser than the pivot, whereas those on the right sie are greater than the pivot. Now the pivot element is placed in the correct position. Now the quick sort procedure is applied for left array and right array in a recursive manner.

void qsort (int A[ ] , int left, int right)
{
int i,j, temp, pivot;

if(left{
pivot = left;
i = left + 1;
j = right;
while(i{
while(A[pivot]>=A[j])
i++;
while(A[pivot]j--;
if(i{
temp=A[j];
A[i]=A[j];
A[j]=temp;
}
}
temp = A[pivot];
A[pivot] = A[j];
A[j]=temp;
qsort(A,left,j-1);
qsort(A,j+1,right);
}
}

Example: Consider an unsorted array as follows40         20         70          14          60           61            97          30Here pivot = 40

40      20      70      14      60      61      97      30

40      20      70      14      60      61      97      30

40      20      30      14      60      61      97      70

Pass 1:

14      20      30      40      60      61      97      70

Now the pivot element reached its correct position. The elements lesser than pivot {14     20       30} is considered as left sub array. The elements than the pivot { 60     61     97     70} is considered as right sub array. Then the Qsort procedure is applied recursively for both these arrays.

Analysis of Quick Sort

Worst Case Analysis                 - O(N²)

Best Case Analysis                   - O (N log N)

Average Case Analysis              - O (N log N)

Advantages of Quick Sort

It is faster than other O(N log N) algorithms.

It has better cache performance.

Limitations

It requires extra memory space.

It requires more processing time.

Data Structures ---- Sorting (Part - 2 Shell Sort)

Shell Sort

reference: PANIMALAR ENGINEERING COLLEGE NOTES
                 Shell sort was invented by Donald Shell. It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time.
                 In this sort the whole array is first fragment into K segments, where K is preferably a prime number. After first pass, the whole array is partially sorted. In the next pass, the value of K is reduced which increases the size of the segment and reduces the number of segments.
                 The next K value is chosen as relatively prime to its previous value. The process is repeated until k=1 at which the array is sorted. The insertion sort is applied to each segment, so each successive segment is partially sorted.The shell sort is also called as Diminishing Increment Sort, because the value of K decreases continuously.

Algorithm

void ShellSort (ElementType A[ ], int N)
{
int i,j,Increment;
ElementType temp;
for(Increment = N/2; Increment>0; Increment = Increment/2)
for(i=Increment;i{
temp=A[i];
for(j=i;j>=Increment;j=j-Increment)
if(tempA[j] = A[j- Increment];
else
break;
A[j] = temp;
}
}

Example

Consider an Unsorted array

81      94       11         96        12       35        17        95        28         58

Here N = 10, the first Pass as K = 5 (10/2)

After First Pass

35        17          11           28           12            81             94            95           96           58

In second pass, K is reduced to 3

After Second Pass

28        12         11           35           17                81               58            95             96            94

In third pass, K is reduced to 1

The final sorted array is

11           12          17          28          35            58            81           94            95           96

Analysis of Shell Sort

Worst Case Analysis                          - O(N²)
Best Case Analysis                             - O(N log N)
Average Case Analysis                       - O(N²)

Advantages of Shell Sort

It is one of the fastest algorithm for sorting small number of elements.

It requires relatively small amounts of memory.

(contd)

Data Structures --- Sorting (PART-1 INTRO + INSERTION SORT) REFERENCE: PANIMALAR ENGINEERING COLLEGE NOTES

A sorting algorithm is an algorithm that puts element of a list in a certain order (ascending or descending).

Sorting Algorithm are often classified by :

• Computational complexity (worst, Average, Best cases) in the term of size of the list n.

                                             Best case     : O(nlogn)

                                              Worst case  : O(n²)

                                             Average case : O(n)

• Memory utilizations
• Number of comparisons
• Method applied like Insertion, exchange, selection, merging etc.

Sorting techniques are categorized into

                                               Internal Sorting

                                               External Sorting

Internal Sorting takes place in the main memory of a computer

Example : Insertion sort, Bubble sort, Shell sort, Quick sort, Heap sort, Merge sort, Radix(Bucket) sort.

External Sorting takes place in the secondary memory of a computer.

Example: Multiway Merge, Poluphase Merge, Replacement Selection, 2-way Merge

INSERTION SORT

Insertion sorts work by taking elements from the list one by one and inserting them into their current position into a new sorted list. Insertion sort consists of N-1 passes, where N is the number of elements to be sorted.

In the insertion sort the element in the position P is saved in tmp and all larger elements prior to position P are moved one spot to the right. The tmp is placed in the correct spot.

Algorithm

void InsertionSort (ElementType A[], int B)

{

int j,P;

ElementType tmp;

for(P=i;P

{

Tmp = A[P];

for(j = P; j>0 && A[j-1]>temp; j--)

A[j] = A[j-1];

A[j] = temp;

}

}

Example

Consider an unsorted array as follows:

34    8   64    51     32      21                                      where (N = 6)

Original	34	8	64	51	32	21	Positions Moved
Pass = 1	8	34	64	51	32	21	1
Pass = 2	8	34	64	51	32	21	0
Pass = 3	8	34	51	64	32	21	1
Pass = 4	8	32	34	51	64	21	3
Pass = 5	8	21	32	34	51	64	4

The final Sorted array : 8     21        32        34        51        64       

Analysis of Insertion Sort

Worst Case Analysis               -- O(N²)

Best Case Analysis                 -- O(N)

Average Case Analysis           -- O(N²)

Limitations of Insertion Sort

It is relatively efficient for small lists and mostly sorted lists.

It is expensive because of shifting all following elements one by one.

                                                                                                                                         (Contd.....)