• 0

Shell Sort Vs Heap Sort Vs Quick Sort


Question

i am having a debate as to which of the sort is more efficient in 2 cases:

when a 2d array of size 50, 100, or 1000 of randomly generated integers

and the same 2d array with all numbers sorted but only 2 indexes where their values have been exchanged.

for these 2 cases which of the 3 sorts seems more efficient.. i am pretty sure the quick sort is the best for the randomly generated array..

but what about the other case... the problem that is bugging me is that when the size is small the difference in the number of comparisons made with quick sort is very similar to the shell sort ...

any suggestions welcomed

:wacko:

Link to comment
https://www.neowin.net/forum/topic/51421-shell-sort-vs-heap-sort-vs-quick-sort/
Share on other sites

9 answers to this question

Recommended Posts

  • 0

In general, quicksort is the fastest known sort method.

However, if the array is presorted, or nearly presorted, then quicksort is no longer the best (the time taken is not much different from random data which is O(n log n)). Shell sort should be quite a bit quicker. Strangely enough, insertion sort and bubble sort - the two algorithms that are taught first 'cause they're so simple - do really well with presorted input (both O(n)). I suspect that in your case ("all numbers sorted but only 2 indexes where their values have been exchanged") insertion sort will be fastest, even faster than shell sort.

Of course I could be wrong ;)

BTW, Heap sort is never any good - don't use it :)

  • 0
  Quote
Big O notation isnt as exact as you are talking about.

Of course it's not exact. On the other hand, for large data sets, any difference in complexity (ie. big-oh) makes a huge difference. Anyway, for the case he's talking about (sorting an almost sorted array) I'm pretty sure shell sort, bubble sort and insertion sort are all O(n). Which makes big-oh notation somewhat useless really. But my guess is that insertion sort will perform the best, due to the simplicity of the algorithm.

  • 0

Also of note: according to my data structures book, shellsort (with Sedgewick's increments) performs better than quicksort when the data set is small (about 100 items or less).

The full results are posted below (the input data is random and the times are in seconds).

post-47-1038033898.gif

  • 0

yeah, what are they

i am doing data structure and i have done discrete mathematics

but what is discrete structures?? :D

from my program it seems like quick sort performed the best in all the cases.

heap sort is disastrous

its time just explodes ...

btw, here is the program which performs these sorts and counts the number of times each sort does a compare and a move ..

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define ARYSIZE 1000
#define ROW 5
#define COL 10
#define SWAP1 19
#define	SWAP2 20
#define NUMTOPRINT 50
#define S "Shell Sort"
#define H "Heap Sort"
#define Q "Quick Sort"

void printSortLine (char *str);
void createAry (int *ary);
void printAry (int *ary, int size);
void shellSort (int list [], int last, int *compare, int *moves);
void printCmpAndMov (int compare, int moves, char *str);
void swap (int *ary);
void heapSort (int list[], int last, int *compare, int *move);
void quickSort (int sortData [], int left, int right, int *compare, int *move);

int main (void)
{
	int ary[ARYSIZE], heapAry [ARYSIZE], quickAry [ARYSIZE], compare = 0, moves = 0;

	createAry (ary);
	memcpy (heapAry, ary, ARYSIZE * sizeof (int));
	memcpy (quickAry, ary, ARYSIZE * sizeof (int));

	printf("Array size:\t%d\n\n", ARYSIZE);

	printSortLine (S);
	compare = moves = 0;
	shellSort (ary, ARYSIZE, &compare, &moves);
	printAry (ary, ARYSIZE);
	printCmpAndMov (compare, moves, "Random list Shell Sort:");
	swap (ary);
	compare = moves = 0;
	shellSort (ary, ARYSIZE, &compare, &moves);
	printCmpAndMov (compare, moves, "Nearly ordered list Shell Sort:");

	printSortLine (H);
	compare = moves = 0;
	heapSort (heapAry, ARYSIZE - 1, &compare, &moves);
	printAry (heapAry, ARYSIZE);
	printCmpAndMov (compare, moves, "Random list Heap Sort:");
	swap (heapAry);
	compare = moves = 0;
	heapSort (heapAry, ARYSIZE - 1, &compare, &moves);
	printCmpAndMov (compare, moves, "Nearly ordered list Heap Sort:");

	printSortLine (Q);
	compare = moves = 0;
	quickSort (quickAry, 0, ARYSIZE - 1, &compare, &moves);
	printAry (quickAry, ARYSIZE);
	printCmpAndMov (compare, moves, "Random list Quick Sort:");
	swap (quickAry);
	compare = moves = 0;
	quickSort (quickAry, 0, ARYSIZE - 1, &compare, &moves);
	printCmpAndMov (compare, moves, "Nearly ordered list Quick Sort:");

	return 0;
}

void printSortLine (char *str)
{
	printf("\nPerforming %s....\n\n", str);
	return;
}

void createAry (int *ary)
{
	int i;

	for (i = 0; i < ARYSIZE; i++)
	{
  ary[i] = rand () % 1001;
	}
	return;
}

void printAry (int *ary, int size)
{
	int i, j;

	if (size <= NUMTOPRINT)
	{
  for (i = 0; i < ROW; i++)
  {
 	 for (j = 0; j < COL; j++)
 	 {
    printf("%4d   ", ary[(i * COL) + j]);
 	 }
 	 printf("\n");
  }
	}
	printf("\n");
	return;
}

void printCmpAndMov (int compare, int moves, char *str)
{
	printf("%-25s\t|compares = %6d  |  moves = %6d|\n", str, compare, moves);
	return;
}

void swap (int *ary)
{
	int temp;

	temp = ary[SWAP1];
	ary [SWAP1] = ary [SWAP2];
	ary [SWAP2] = temp;
	return;
}

void shellSort (int list [], int last, int *compare, int *moves)
{
	int hold, incre, curr, walker;

	incre = last / 2;
	while (incre != 0)
	{
  for (curr = incre; curr <= last; curr++)
  {
 	 hold = list [curr];
 	 *moves += 1;
 	 walker = curr - incre;
 	 while (((*compare)++,walker >= 0 && hold < list [walker]))
 	 {
    list [walker + incre] = list [walker];
    *moves += 1;

    walker = (walker - incre);
 	 }

 	 list [walker + incre] = hold;
 	 *moves += 1;
  }
  incre /= 2;
	}
	return;
}


void heapSort (int list[], int last, int *compare, int *move)
{
	void reheapUp (int heap[], int newElem, int *compare, int *move);
	void reheapDown (int heap[], int current, int last, int *compare, int *move);

	int sorted, holdData, walker;

	for (walker = 1; walker <= last; walker++)
	{
  reheapUp (list, walker, compare, move);
	}

	sorted = last;
	while (sorted > 0)
	{
  holdData = list [0];
  list [0] = list [sorted];
  list [sorted] = holdData;
  *move += 3;
  sorted--;
  reheapDown (list, 0, sorted, compare, move);
	}
	return;
}

void reheapUp (int *heap, int newNode, int *compare, int *move)
{
	int parent, hold;

	if (newNode)
	{
  parent = (newNode - 1)/2;
  if ( *compare += 1, heap [newNode] > heap [parent])
  {
 	 hold = heap[parent];
 	 heap[parent] = heap[newNode];
 	 heap[newNode] = hold;
 	 *move += 3;
 	 reheapUp (heap, parent, compare, move);
  }
	}
	return;
}

void reheapDown (int *heap, int root, int last, int *compare, int *move)
{
	int hold, leftKey, rightKey, largeChildKey, largeChildIndex;

	if ((root * 2 + 1) <= last)
	{
  leftKey = heap [root * 2 + 1];
  *move += 1;

  if ((root * 2 + 2) <= last)
  {
 	 rightKey = heap [root * 2 + 2];
 	 *move += 1;
  }
  else
  {
 	 rightKey = -1;
  }

  if (leftKey > rightKey)
  {
 	 largeChildKey = leftKey;
 	 largeChildIndex = root * 2 + 1;
  }
  else
  {
 	 largeChildKey = rightKey;
 	 largeChildIndex = root * 2 + 2;
  }

  if (*compare += 1, heap[root] < heap [largeChildIndex])
  {
 	 hold = heap [root];
 	 heap [root] = heap [largeChildIndex];
 	 heap [largeChildIndex] = hold;
 	 *move += 3;
 	 reheapDown (heap, largeChildIndex, last, compare, move);
  }
	}
	return;
}

void quickSort (int sortData [], int left, int right, int *compare, int *move)
{
#define MIN_SIZE 16

	void quickInsertion (int sortData[], int first, int last, int *compare, int *move);
	void medianLeft (int sortData[], int left, int right, int *compare, int *move);

	int sortLeft;
	int sortRight;
	int pivot;
	int hold;

	if ( (right - left) > MIN_SIZE)
	{
  medianLeft (sortData, left, right, compare, move);
  pivot = sortData [left];
  *move += 1;
  sortLeft = left + 1;
  sortRight = right;

  while (sortLeft <= sortRight)
  {
 	 while (*compare += 1, sortData [sortLeft] < pivot)
    sortLeft = sortLeft + 1;

 	 while (*compare += 1, sortData[sortRight] >= pivot)
    sortRight = sortRight - 1;

 	 if (sortLeft <= sortRight)
 	 {
    hold = sortData [sortLeft];
    sortData [sortLeft] = sortData [sortRight];
    sortData [sortRight] = hold;
    *move += 3;
    sortLeft = sortLeft + 1;
    sortRight = sortRight - 1;
 	 }
  }

  sortData [left] = sortData [sortLeft - 1];

  sortData [sortLeft - 1] = pivot;

  *move += 2;

  if (left < sortRight)
 	 quickSort (sortData, left, sortRight - 1, compare, move);
  if (sortLeft < right)
 	 quickSort (sortData, sortLeft, right, compare, move);
	}
	else
  quickInsertion (sortData, left, right, compare, move);
	return;
}

void quickInsertion (int sortData[], int first, int last, int *compare, int *move)
{
	int current;
	int hold;
	int walker;

	for (current = first + 1; current <= last; current++)
	{
  hold = sortData [current];
  *move += 1;
  walker = current - 1;
  while (*compare += 1, walker >= first && hold < sortData [walker])
  {
 	 sortData [walker + 1] = sortData [walker];
 	 *move += 1;
 	 walker = walker - 1;
  }
  sortData[walker + 1] = hold;
  *move += 1;
	}
	return;
}

void medianLeft (int sortData[], int left, int right, int *compare, int *move)
{
	int mid;
	int hold;

	mid = (left + right) / 2;

	if (*compare += 1, sortData [left] > sortData [mid])
	{
  hold = sortData [left];
  sortData [left] = sortData [mid];
  sortData [mid] = hold;  
  *move += 3;
	}
	if (*compare += 1, sortData [left] > sortData [right])
	{
  hold = sortData [left];
  sortData [left] = sortData [right];
  sortData [right] = hold;
  *move += 3;
	}
	if (*compare += 1, sortData [mid] > sortData [right])
	{
  hold = sortData [mid];
  sortData [mid] = sortData [right];
  sortData [right] = hold;
  *move += 3;
	}

	hold = sortData [left];
	sortData [left] = sortData [mid];
	sortData [mid] = hold;
	*move += 3;

	return;
}

here is the output file

  Quote
output# 1

Array size:     50

Performing Shell Sort....

 18     41    117    126    150    153    225    258    273    291

292    303    328    329    359    370    404    431    440    442

449    467    474    491    527    590    642    656    660    675

698    699    700    704    705    709    757    788    811    823

862    868    876    885    893    899    931    936    952    993

Random list Shell Sort:         |compares =    372  |  moves =    580|

Nearly ordered list Shell Sort: |compares =    209  |  moves =    417|

Performing Heap Sort....

 18     41    117    126    150    153    225    258    273    291

292    303    328    329    359    370    404    431    440    442

449    467    474    491    527    590    642    656    660    675

698    699    700    704    705    709    757    788    811    823

862    868    876    885    893    899    931    936    952    993

Random list Heap Sort:          |compares =    269  |  moves =   1140|

Nearly ordered list Heap Sort:  |compares =    361  |  moves =   1467|

Performing Quick Sort....

 18     41    117    126    150    153    225    258    273    291

292    303    328    329    359    370    404    431    440    442

449    467    474    491    527    590    642    656    660    675

698    699    700    704    705    709    757    788    811    823

862    868    876    885    893    899    931    936    952    993

Random list Quick Sort:         |compares =    294  |  moves =    306|

Nearly ordered list Quick Sort: |compares =    155  |  moves =    105|

Output# 2

Array size:     100

Performing Shell Sort....

Random list Shell Sort:         |compares =    916  |  moves =   1425|

Nearly ordered list Shell Sort: |compares =    510  |  moves =   1019|

Performing Heap Sort....

Random list Heap Sort:          |compares =    642  |  moves =   2756|

Nearly ordered list Heap Sort:  |compares =    910  |  moves =   3685|

Performing Quick Sort....

Random list Quick Sort:         |compares =    712  |  moves =    731|

Nearly ordered list Quick Sort: |compares =    410  |  moves =    213|

Output# 3

Array size:     1000

Performing Shell Sort....

Random list Shell Sort:         |compares =  15493  |  moves =  23508|

Nearly ordered list Shell Sort: |compares =   8015  |  moves =  16030|

Performing Heap Sort....

Random list Heap Sort:          |compares =   9733  |  moves =  43757|

Nearly ordered list Heap Sort:  |compares =  15325  |  moves =  61177|

Performing Quick Sort....

Random list Quick Sort:         |compares =  10982  |  moves =   9177|

Nearly ordered list Quick Sort: |compares =   7032  |  moves =   2205|

  • 0

quick sort is the fastest when u have huge test cases. (i learnt that half way through a programming competition, bad day that was)

shell sort and merge sort would serve ur purpose the rest of the time.

heapsort, bubble sort, selection sort are practically useless.

thats wat i feel.

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Posts

    • From cars to cosmos: Honda's experimental rocket aces first landing test by Paul Hill Image via Honda Watch your back SpaceX, the Japanese company Honda has just performed a successful first launch of its experimental reusable rocket. The 6.3 meter rocket, which weighs 900kg, reached a modest altitude of 271.4 meters, but managed to land within 37cm of its target (1.2 feet), which is certainly pretty close. The rocket took off from a Honda facility in Taiki Town, Hokkaido, a growing space town in Japan. The flight time was also modest, coming in at just 56.6 seconds, but in that time, Honda was able to demonstrate key reusability technologies such as flight stability and landing capability. This marks a significant milestone for Honda’s space R&D department, which began work just four years ago. If you remember the tests SpaceX was performing around 2012 with Grasshopper, well Honda is at about the same stage with its reusable rocket. Why Honda is building rockets: Beyond cars and motorcycles Honda said that it wants to leverage core technologies it already works on for offering space services. It said that reusable rockets are a key part of sustainable space transportation. By 2029, the company wants to be able to perform suborbital launches, and while commercialization hasn’t been decided yet, it sees itself launching remote-sensing and wide-area communication satellites in the future. The Japanese car maker sees growing demand for satellite launches and wants to be involved by developing reusable rockets which could help it perform such launches economically. If it does end up finding customers, it will add more competition to the rocket launch sector. While the company hasn’t confirmed this, by developing its own launch system, it could eventually be in a position to launch its own satellites that could provide services to its cars to add value for customers. The competitive landscape and Japan's space ambitions Honda is just the latest company to join the growing list of companies trying to develop reusable rocket technology. The most famous companies doing this are SpaceX and Blue Origin, but there are also lots of other companies around the world also developing this technology. Honda is still taking baby steps compared to SpaceX, but it shows that the company is taking a focused, step-by-step approach, and achieving successes as noted by this launch. Hopefully, the company ends up providing tough competition against SpaceX, Blue Origin, and other companies so that it can help to drive down prices and spur on innovation.
    • Does that subscription include international data roaming, inclusive of Russia?
    • If you're stupid enough to try and get one, each and every headache along the way is on you. I can only hope that these roadblocks on a pre-order are enough to dissuade people.
    • "You should have a Microsoft Account because we can help keep your data safe...until we can't." As an IT guy I know that I should never put my trust in one backup solution if the data is important. But for non-IT people, they are getting tricked into Microsoft's practices with falsehoods.
    • it is delayed and has no definitive release date... that is "delayed indefinitely".
  • Recent Achievements

    • Week One Done
      TBithoney earned a badge
      Week One Done
    • First Post
      xuxlix earned a badge
      First Post
    • First Post
      Tomek Święcicki earned a badge
      First Post
    • One Year In
      carlitin86 earned a badge
      One Year In
    • Reacting Well
      Peterlll06 earned a badge
      Reacting Well
  • Popular Contributors

    1. 1
      +primortal
      684
    2. 2
      ATLien_0
      289
    3. 3
      Michael Scrip
      228
    4. 4
      +FloatingFatMan
      192
    5. 5
      Steven P.
      145
  • Tell a friend

    Love Neowin? Tell a friend!