Introduction to Arrays Sorting

• Introduction about Array

Array is a sequence collection of elements are of same type.The elements of array are accessed by index.
Array can be 1 dimensional or n dimensional.

In C Array declaration is in the form:
char name[100];

Here char is the data type and name is the base pointer of array.
The Base pointer of array cannot be changed.The Compiler treats it has constant pointer.

Array is used in application like storing list of records. etc
Arrays are used to implement various types of programs and algorithms like sorting,tress,Graphs etc.

• Merging two sorted list

Algorithm
1) Take three Arrays A1,A2 and C1.
2)Compare each elements of A1 with A2,During comparing of elements,if 1st less than 2nd one,Then insert the 1st one C1 else 2nd one into C1. The Array from which the element is taken for insertion in third list,Increment the index of that Array.
3)Repeat step 2 for all the elements in the Array.If you get Nth index in any of the Array then go to step 4.
4) Insert the non finished Array directly in the Third array.
4) The third Array contains the list of sorted elements.

• Bubble Sort

1) take a array and Compare first two elements,If greater swap with other element.So at last we get largest element in nth location.
So no of Comparisons required is n-1 first time.

Like that total comparisons are (n-1)+(n-2)+--------1= n(n-1)/2.
Order = O(n^2);

• Quick Sort

1)Quick sort is the fastest sorting algorithm.
2)Take a Array of elements.Consider the first element as pivot.
3) traverse from left if the current element is greater than pivot,stop there.
4) traverse the list from right,if no is less than pivot,wait there.
4)Swap the two wait locations elements.
5) traverse the list again until their traverse won't cross with each other.
6) always traverse from left first.
7) if they cross with each other,swap the right location value with pivot.
8) two lists are formed now.
8) 0 to right and left to n-1.
9) perform quick sort again on two lists.

Average time complexity of Quick sort is O(nlogn).
worst case time complexity = O(n^2). ( always one of list is empty).
worst case space complexity =O(n). ( every time list splits into two).

• Selection Sort

1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for remainder of the list.

Timing Complexity: worst=best=average=O(n^2).