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]

Pass 1

A[0] A[1] A[2] A[3] A[4]

Min Loc

There for interchange A[0] & A[2]

Pass 2

A[0] A[1] A[2] A[3] A[4]

min Loc

There for interchange A[1] & A[4]

Pass 3

A[0] A[1] A[2] A[3] A[4]

min Loc

There for interchange A[2] & A[3]

Pass 4

A[0] A[1] A[2] A[3] A[4]

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 ( n²)

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

0 1 2 3 4 5 6

Pass I: a[1]<a[0], interchanging the position of elements, we get.

0 1 2 3 4 5 6

Pass-spacerun:yes"> II: a[2]>a[0], position of element remain same

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

0 1 2 3 4 5 6

Pass IV : a[4]> a[3], no chanage is performed.

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

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 :

0 1 2 3 4 5 6

After the pass VI ,we get array with sorted elements.n>

1. Algorithm of Insertion Sort

Set k =
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]

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];

{

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

Wednesday 14 March 2018