Shell sort and Heap sort algorithm in C programming language.

Shellsort is a multi-pass algorithm. Each pass is an insertion sort of the sequences consisting of every h-th element for a fixed gap h (also known as the increment). This is referred to as h-sorting. Shell sort is unstable,that is, it may change the relative order of elements with equal values.It has “natural” behavior, in that it executes faster when the input is partially sorted.

Shell Sort C Code And Algorithm
Shell Sort In Action

Algorithm/Pseudo-Code:

 
Using Marcin Ciura’s gap sequence, with an inner insertion sort.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* Double-Click To Select Code */
# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]
 
foreach (gap in gaps)
{
    # Do an insertion sort for each gap size.
    for (i = gap; i < n; i += 1)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    }
}



C Code for Shell Sort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/* Double-Click To Select Code */
#include <stdio.h>
#include <conio.h>
#define MAX 20
voidmain()
{
 intarr[MAX],i,j,k,n,increment;
 clrscr();
 printf("Enter the number of elements: ");
 scanf("%d",&n);
 printf("\nEnter %d elements : \n",n);
 for(i=0 ; i<n ; i++)
 scanf("%d",&arr[i]);
 printf("\nUnsorted list is:\n");
 for(i = 0; i < n; i++)
 {
  printf("%4d",arr[i]);
 }
 increment=5;
 /*ACTUAL LOGIC STARTS*/
 while(increment>=1)
 {
  for(j=increment ; j<n ; j++)
  {
   k=arr[j];
   for(i = j-increment ; i >= 0 && k<arr[i] ; i = i-increment)
   arr[i+increment]=arr[i];
   arr[i+increment]=k;
  }
  increment=increment-2;  /*Decrease the incrementement*/
 }
 printf("\n\nSorted list is:\n");
 for(i = 0 ; i<n ; i++)
 {
  printf("%4d",arr[i]);
 }
 printf("\n\n *www.electromaniaweb.wordpress.com*");
 getch();
}

 

 

 

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), Heapsort is an in-place algorithm, but it is not a stable sort.

Implementation:

The heapsort algorithm can be divided into two parts.

In the first step, a heap is built out of the data.

In the second step, a sorted array is created by repeatedly removing the largest element from the heap, and inserting it into the array. The heap is reconstructed after each removal. Once all objects have been removed from the heap, we have a sorted array. The direction of the sorted elements can be varied by choosing a min-heap or max-heap in step one.

Heapsort can be performed in place. The array can be split into two parts, the sorted array and the heap.  The heap’s invariant is preserved after each extraction, so the only cost is that of extraction.

Algorithm & Pseudo Code For Heap Sort:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

/* Double-Click To Select Code */

function heapSort(a, count) is

     input:  an unordered array a of length count

     (first place a in max-heap order)

     heapify(a, count)

     end := count-1

    /* In languages with zero-based arrays the children are 2*i+1 and 2*i+2 */

     while end > 0 do

         (swap the root(maximum value) of the heap with the last element of the heap)

         swap(a[end], a[0])

         (decrease the size of the heap by one so that the previous max value will

         stay in its proper placement)

         end := end – 1

         (put the heap back in max-heap order)

         siftDown(a, 0, end)

 function heapify(a, count) is

     (start is assigned the index in a of the last parent node)

     start := (count – 1) / 2

     while start ≥ 0 do

         (sift down the node at index start to the proper place such that all nodes

          below the start index are in heap order)

         siftDown(a, start, count-1)

         start := start – 1

     (after sifting down the root all nodes/elements are in heap order)

 function siftDown(a, start, end) is

     input:  end represents the limit of how far down the heap

                   to sift.

     root := start

     while root * 2 + 1 ≤ end do          (While the root has at least one child)

         child := root * 2 + 1        (root*2 + 1 points to the left child)

         swap := root        (keeps track of child to swap with)

         (check if root is smaller than left child)

         if a[swap] < a[child]

             swap := child

         (check if right child exists, and if it’s bigger than what we’re

          currently swapping with)

         if child+1 ≤ end and a[swap] < a[child+1]

             swap := child + 1

         (check if we need to swap at all)

         if swap != root

             swap(a[root], a[swap])

             root := swap          (repeat to continue sifting down the child now)

         else

             return

 

C Program For Quick Sort:

?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

/* Double-Click To Select Code */

#include<stdio.h>

#include<conio.h>

void heapsort(int[], int);

void heapify(int[], int);

void adjust(int[], int);

int main()

{

 int array[50],n,i;

 clrscr();

 printf(“Enter the no. of elements to be sorted: “);

 scanf(“%d”,&n);

 printf(“\nEnter the elements: \n”);

 for(i=0 ; i<n ; i++)

 scanf(“%d”,&array[i]);

 printf(“\nBefore Heapsort:”);  //Array Before Mergesort

 for(i = 0; i < n; i++)

 {

  printf(“%4d”, array[i]);

 }

 printf(“\n”);

 heapsort(array,n);

 printf(“\nAfter Heapsort:”);  //Array After Mergesort

 for(i = 0; i < n; i++)

 {

  printf(“%4d”, array[i]);

 }

 printf(“\n”);

 getch();

 return 0;

}

void heapsort(int array[], int n)

{

 int i,t;

 heapify(array,n);

 for(i=n-1 ; i>0 ; i–)

 {

  t = array[0];

  array[0] = array[i];

  array[i] = t;

  adjust(array,i);

 }

}

void heapify(int array[], int n)

{

 int item,i,j,k;

 for(k=1 ; k<n ; k++)

 {

  item = array[k];

  i = k;

  j = (i-1)/2;

  while( (i>0) && (item>array[j]) )

  {

   array[i] = array[j];

   i = j;

   j = (i-1)/2;

  }

  array[i] = item;

 }

}

void adjust(int array[], int n)

{

 int item,i,j;

 j = 0;

 item = array[j];

 i = 2*j+1;

  while(i<=n-1)

 {

  if(i+1 <= n-1)

   if(array[i] < array[i+1])

    i++;

  if(item < array[i])

  {

   array[j] = array[i];

   j = i;

   i = 2*j+1;

  }

  else

   break;

 }

 array[j] = item;

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s