• 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

    • Harmful to them because it affects their business. *Sigh*
    • TCL 75" 4K Smart TV hits lowest price, now less than £500 by Paul Hill Are you in the UK and looking for a massive 75-inch Ultra HD 4K HDR TV at a relatively affordable price? If so, check out this TCL (75P755K) 75-inch TV now because it’s at its lowest price of just £499.00, down 15% from £589.00. The model in question is slightly older, from 2024, but it’s still an excellent home entertainment upgrade given its feature set and aggressive price point. What you get: Features for the price The feature set of this model is definitely pretty impressive. It supports 4K HDR, wide colour gamut, and multiple HDR formats including HDR10+ and Dolby Vision. It also leverages MEMC (Motion Estimation & Motion Compensation), a proprietary algorithm from TCL that helps to reduce motion display blur and keep motion trails to a minimum. While MEMC will do heavy lifting to ensure the best picture, the TV only has a 60Hz refresh rate, but an effective rate of 120Hz thanks to efforts by TCL. This TCL model features Dolby Atmos 2.0 that immerses you more in whatever you’re watching on the TV. In terms of software, this TV comes with Google TV (based on Android) which is well-known and widely supported, ensuring you can use all the apps you depend on. It also supports Google Assistant, Chromecast, and voice control. The Chromecast support allows you to easily stream from your computer or phone to the TV to share what you’re watching to the people around you. The Google Assistant support can also be good if you have smart home devices around the house that can connect to it. The audio features for this TV are also good and mean you don’t need to buy a separate sound bar immediately. User experience and potential considerations According to What Hi-Fi, which reviewed the smaller 65-inch version of this TV, TCL’s TV delivers when it comes to HDR; gaming features such as low input lag, VRR, and Game Bar; wide colour gamut, and the operating system. What it didn’t like about the TV was the limited brightness, which degraded the HDR in bright rooms; the average motion handling; the lack of bass; the lack of local dimming; and the budget-oriented build quality. Making the smart buy decision If you can overlook its limitations, this TV could be a good pick if you need a new TV in the living room on a budget. If you are a serious gamer looking for a high refresh rate, or someone in a very bright room, then you will probably want to look elsewhere. Amazon is also offering free add-on services including wall mounting and unpack. If you do decide to pick up this TCL TV and find a fault with it, you have 30-days from getting the receipt to return it. TCL 75P755K 75-inch 4K TV: £499 (Amazon UK) - MSRP £589 / 15% off This Amazon deal is U.K. specific, and not available in other regions unless specified. If you don't like it or want to look at more options, check out the Amazon UK deals page here. Get Prime, Prime Video, Music Unlimited, Audible or Kindle Unlimited, free for the first 30 days As an Amazon Associate we earn from qualifying purchases.
    • I came here to post something similar, you beat me to it. Why on earth would somebody buy Windows again, even this shady grey-market cheap key, when they already have it and an upgrade from 10 to 11 is free?
    • I maintain that the Cybertruck was a social experiment.  "Can we convince the massively insecure petrol guzzling, Dodge Ram loving, right wing idiots to buy a poorly built, underpowered, underspecified, electric vehicle that they know everyone will laugh at them in"
  • Recent Achievements

    • Week One Done
      theevergreentree earned a badge
      Week One Done
    • Dedicated
      Fryer Tuck earned a badge
      Dedicated
    • Week One Done
      luxoxfurniture earned a badge
      Week One Done
    • First Post
      Uranus_enjoyer earned a badge
      First Post
    • Week One Done
      Uranus_enjoyer earned a badge
      Week One Done
  • Popular Contributors

    1. 1
      +primortal
      439
    2. 2
      +FloatingFatMan
      247
    3. 3
      snowy owl
      226
    4. 4
      ATLien_0
      212
    5. 5
      Xenon
      152
  • Tell a friend

    Love Neowin? Tell a friend!