Wednesday, 14 March 2018

Beginners guide to data structures

What is data structure ?
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.
Data may be organized in many different ways the logical or mathematical model of a particular organization of data is called a data structure.

Sorting ->

Sorting is a basic operation of computer science. Sorting refers to the operation of arranging data in some given sequence i.e., increasing or decreasing order.

Bobble Sort ->

In the bubble sort, each element is compared with its adjacent element. If the first element is larger than second one then the position of the elements are interchanged otherwise it is not changed. The next element is compared with its adjacent element and the same process is repeated for all the elements in the array during the next pass the same process is the largest leaving the largest element. Suring the pass the second largest element occupies the second last position. During the next pass the same process is repeated leaving the largest element. The same process is repeated until no more elements are left for comparison. Finally the array is sorted one.
The various steps involved in sorting of an array of 5 elements given below:
Initial elements
12, 16, 3, 14, 7,

First Pass
12 16 3 14 7 no swapping
12 3 16 14 7 swapped
12 3 14 16 7 swapped
12 3 14 7 16 swapped
Second Pass
3 12 14 7 16 Swapped
3 12 14 7 16 no swapping
3 12 7 14 16 swapped
3 12 7 14 16 no swapped
Third Pass 3 12 7 14 16 no swapping
3 7 12 14 16 swapped
3 7 12 14 16 no swapping
3 7 12 14 16 no swapping
Algorithm : Bubble Sort a[n] This algorithm sorts the Array a with N element
Initialization Set
I=0
Repeat steps 3 to 5 until I Set J=0
Repeat step 5 until j If a[J]>a[J+1] then
Set temp = a[J]
Set a[J] = a[J + 1]
Set a[J+1] = temp
End if
6. Exit
Function is C language for Bubble Sort.
void bubble_sort(int a[], int n)
{ int temp, i, j;
for( i = 0 ; i < n; i++)
{
for( j = 0; j < n -i -1; j++)
{
if(a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}

Analysis of bubble
Sort In the Bubble sort, the first pass requires (n-1) comparisons to fix the highest element to its location, the second pass require (n-2)…, kTh pairs requires (n-k) and the last pass requires only one comparison to be fixed at its proper position. There for the total comparisons are
F(n) = (n - 1) + (n - 2) + (n - 3) +…+ (n - k) + 3 + 2 + 1 = n(n - 1)/2
F(n) = O ( n2)

Selection Sort

The selection sort technique is based upon the extension of the minimum / maximum technique. By means of a nest of for loops, a pass through the array is made to locate the minimum value. Once this found, it is placed in the first position of the array. Another position and so on. Once the next to last element is compared with the last element, all the elements have been sorted into ascending order:
   A[0]                          A[1]                         A[2]                          A[3]                          A[4]
17
16
3
14
7
Pass 1
   A[0]                          A[1]                         A[2]                          A[3]                          A[4]
17
16
3
14
7
Min                                                               Loc
There for interchange A[0] & A[2]

Pass 2
   A[0]                          A[1]                         A[2]                          A[3]                          A[4]
3
16
17
14
7
                                    min                                                                                             Loc
There for interchange A[1] & A[4]

Pass 3
   A[0]                          A[1]                         A[2]                          A[3]                          A[4]
3
7
17
14
16
                                                                     min                           Loc
There for interchange A[2] & A[3]

Pass 4
   A[0]                          A[1]                         A[2]                          A[3]                          A[4]
3
7
14
17
16
                                                                                                       min                           Loc
There for interchange A[3] & A[4]

Algorithm of Selection Sort

Function for selection Sort
Void selection_sort(int a[], int n)
{
        Int min, loc, temp, I, j;
        min=a[o];
        for(i=0;i<n-1;i++)
        {
                min=a[i];
                loc=i;
                for(j=i+1;j<n-1;j++)
                {
                           If(a[j]<min)
                           {
                                 min = a[j];
                                 loc=j;
                           }
                 }
                if(loc!=i)
                {
                     temp = a[i];
                     a[i] = a[loc];
                     a[loc] = temp;
                }
         }
}
F(n) = (n - 1) + (n - 2) + (n - 3) +…+ (n - k) + 3 + 2 + 1
        = n(n - 1)/2
        = O ( n2)

Insertion Sort
An insertion sort is one that sorts a set of values by inserting values into an existing sorted file.
      
       Suppose an array a with n elements a[1], a[2],….,a[n] is in memory. The insertion sort algorithms scans a from a[1] to a[n],inserting each element a[k] into its proper position in the previously sorted sub array a[1],a[2],….,a[k-1].That is:
Pass 1. a[1] by itself is trivially sorted.
Pass 2. a[2] is inserted either before or after a[1] so that: a[1],a[2] is sorted.
Pass 3. a[3] is inserted into its proper place in a[1], a[2], that is, before a[1], 
between a[1] and a[2],or after a[2],so that: a[1], a[2], a[3] is sorted.
Pass 4. a[4] is inserted into its proper place in a[1], a[2], a[3] so that:
A[1], a[2], a[3], a[4] is sorted.
……………………………………………………………………………………………………………………………………………….
Pass N. a[n] is inserted into its proper place in a[1], a[2],……, a[n-1] so that:
a[1],a[2],….,a[n] is sorted.
To illustrate the insertion sort method, consider the following array a with 7 elements:
25, 15, 30, 9, 99, 20, 26
Array a of 7 elements
        
     25
      15
      30
          9
      99
     20
      26
      0                     1                         2                     3                        4                     5                       6
Pass I:              a[1]<a[0], interchanging the position of elements, we get.
     15 
      25
       30
     9
         99
       20
        26

     0                        1                      2                    3                     4                        5                  6        
Pass-spacerun:yes">  II:          a[2]>a[0], position of element remain same
     15 
      25
       30
     9
         99
       20
        26
     0                         1                       2                   3                          4                     5                      6
Pass  III :     a[3] is less than a[0], a[1] and a[2], so insert a[3] before a[0], we get.
                                   a[5] before a[2], we get
     9
      15
       25
     30
         99
         20
        26
     0                        1                         2                  3                         4                       5                     6
Pass IV :     a[4]> a[3], no chanage is performed.
       9
      15
       25
     30
         99
       20
        26
      0                      1                        2                     3                         4                      5                     6
Pass V:    a[5] is less than a[2], a[3] and a[4], therefore insert a[5] before a[2], we get
     9
      15
       20
     25
         30
       99
        26
      0                        1                      2                    3                          4                   5                        6
Pass Vi:    now a[6] is less than a[4], a[5] therefore insert a[6] before a[4], giving the                          following array :
     9
       15
       20
     25
        26
       30
        99
     0                          1                     2                     3                        4                       5                   6
After the pass VI ,we get array with sorted elements.n>

1. Algorithm of Insertion Sort
  1. Set k =
  2. For k=1 to (n-1)
Set  temp =a[k]
Set  J = k-1
While temp <a[j] and (j>=0) perform
The following steps.
Set a[j+1]= a[j]
[End of loop structure]
Assign the value of temp to a[j+1].
[End of loop structure]                               
  1. Exit.


Functoin for  Insertion Sort


Quick Sort

            It is one of the most popular sorting techniques.Quick sort possesses a very good average case behevior among all the sorting techniques.This is developed by C.A.R. Hoare.
          The quick sort algorithm work by partitioning the array to be sorted.And each partiton is  in turn sorted recursively.In partition,one of the array element is chosen as a key value. This key value can be the first element of an array.That is,If a is an array then key =a[0].And rest of the array element are grouped into two position such that
·         One parition contain element smaller than the key value.
·         Another partiton contain elements larger than the key value.
Figure 10.2 show  a key and partition of element in an array.
Partition 1


Partition  2
                                Values < key                                      key                                       values > key
As an example consider an array with the following elements.
45       26     77      14     68    61    97     39     99      90
           Here , 45 is selected as a key value. then, two indices namely. Low and high are used to indicate the element (key +1) and the last element. The low index starts on the left and select an element that is greater than the key value. Than these elements are interchanged. This process is repeated until all elements to left of the key are greater than the key value.
       The steps involved in placing the key value, 45 in its proper position in the array are given below.The elements being compared are encircled on each line.
                                low
                        45      26         77            14            68             61             97             39       99        90
                                                          low
                         45      26         77             14            68             61             97            39       99        90

                       45      26         77             14            68             61             97            39         99    90high
                                                                                                                                                                  high
                       45      26         77             14            68             61             97            39        99        90           
                                                                                                                                                    high
                       45      26         77             14            68             61             97            39        99        90
                                                                        low
                       45      26         77             14            68             61             97            39        99        90
low
                       45      26         77             14            68             61             97            39        99        90
                                                                                                                                   high
                       45      26         77             14            68             61             97            39        99        90
                                                                                                               high
                       45      26         77             14            68             61             97            39        99        90
high
                       45      26         77             14            68             61             97            39        99        90
                                                                           high
                       45      26         77             14            68             61             97            39        99        90

                    14      26         39          45            68             61             97            77         99       90
                   _______________                     ____________________________________
                           Value < 45                                                              value > 45
 
The given array has been partitioned into two sub arrays. The first sub array is [14,26,39]
And the second sub array is {68,61,97,77,99,90}.We can repeatedly apply with procedure on each of these sub array until the entire array is sorted. Since the array element are partitioned and exchanged, this technique is called partition exchanged technique.

           In the quick sort technique, each time the given array is partition into two smaller sub arrays, each of these sub array can we processed either a iteratively or recursively.

Algorithm of the quick sort.
    
   
Step 1:   [Initially]
                 Low =I
                 High=h
                Key= a[(l + h)/2] [Middle element of
                the element the list]
Step 2:  Repeat through step 7 while
(low<=high)                                                
Step 3: Repeat step 4 while (a([low]<key))
Step 4: low=low+1
Step 5: Repeat Step 6 while a([high]<key))
Step 6: High = high -1
Step 7: if (low<=high)
            (i)  temp = a[low]
            (ii) a[low]=a[high]
            (iii) a [high]=temp
            (iv) low=low+1
            (v) high= high-1
Step 8: if(I<high) Quick _ sort(a, I, high)
Step 9: If(low<h) Quick _ sort(a, low, h)
Step 10: Exit
The c code for recursive function of quick sort is:
     Void quick _ sort( int a[],int I, int h)
    {
    Int temp, key, low, high;
    Low=I;
    High=h;
    Key=a[(low+high)/2];
    Do
    {
      While(key>a[low])
    {
        Low ++;
    }
  While(key<a[high])
 {
      High --;
  }
 If(low<=high)
{
 Temp=a[low];
 A[low++]=a[high];
A[high --]=temp;
}
}
While(low<=high);
If(I<high)
Quick _ sort(a,I,high);
If(low<h)
Quick  _ sort(a, low,h);
}



Efficiency of quick Sort
        The timing analysis of quick sort algorithm is given by the following recurrence relation :
                                                   a               n=1         
                        T(n) =
                                              cn + T(n/2)+T(n/2)

Where ,            cn                time required to partition the array
                    T(n/2)                 time required to sort the left subarray
                    T(n/2)                  time required to sort the right subarray
                  Here time required to partiton the array is O(n).
Worst-case Analysis

MERGE SORT
Merge sort is a sorting technique which divides the array into subarrays pf size 2 and merge adjacent

Pairs.  We then have approximately  n/2 arrays of size 2. This process is repeated until there is only

One only one array remaining of size n.

Suppose an array a with n element [1], a[2],…,a[N] is in memory. The merge-sort algorithm which sorts a will first be described by means of specific example.

    Example: Suppose the array contains 12 element as follows: 85,76,46,92,30,41,12,19,93,3,50,11

Each pass of the merge sort algorithm will start at the beginning of the array A and merge pairs of sorted sub arrays as follow:

Pass 1:  Merge each pair of element to obtain the following list of sorted pairs:

76,85    46,92     30.41     12,19    3,93     11,50

Pass2: Merge each pair of obtain the lists of sorted elements.

46,76,85,92       12,19,30,41      3.11,50,93

 Pass3: Again Merge the two subarrays to get two lists.

12, 19,30,41,46,76,85,92,   3,11,50,93

Pass4: Merging the above lists, we get

3,11,12,19,30,41,46,50,76,85,,92,93


In pass 4, we get sorted list of array with the size of 12

No comments:

Post a Comment

The World's Deepest Swimming Pool

Chania

The largest ever hand-dug excavation in the world

Chania

The Heart River is a tributary of the Missouri River

Chania

Truly Amazing fact

View All