• 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

    • Wish you could set the WiFi country without setting an SSID. This would stop the warning on every boot.
    • Huawei's Mate XT successor launches this year with a performance and camera boost by Hamid Ganji Last year, Huawei reimagined our perception of folding smartphones by launching the world's first tri-folding device, Mate XT. Contrary to regular folding smartphones like the Samsung Galaxy Z Fold 6, the Huawei Mate XT utilizes a dual-hinge mechanism that allows the device to fold into a "Z" shape. The success of the Mate XT has allegedly prompted Huawei to release a sequel this year. Chinese tipster Digital Chat Station on Weibo says Huawei will release a successor in the second half of 2025. While the folding and screen solution remain unchanged, the tipster claims the second-generation Mate XT gets a faster processor and upgraded camera setup. Digital Chat Station says Huawei will also improve the device's accessories. Last year's Mate XT included an Aramid Fiber Case with an integrated rotating stand in the box as official accessories. Though the tipster doesn't mention quality improvements, Huawei could reinforce the phone's folding endurance. As for the release date, the first-generation Mate XT was released in September 2024, and the Mate XT 2 might also be released at the same time. Interestingly, Huawei announced its Mate XT, the world's first tri-folding device, on September 10 last year, just one day after Apple announced its iPhone 16 series. If Huawei wants to tease Apple again, we can expect the Mate XT 2 to drop simultaneously with the iPhone 17 series. While these devices are not in the same category, Huawei's rivalry with Apple is common knowledge. Tri-folding smartphones provide bigger screens at a more compact size compared to tablets. For example, the Huawei Mate XT has a screen size of 10.2 inches when it's fully open and 7.9 inches when folded once. Also, when you fold it twice, you get a 6.4-inch screen like regular smartphones. Huawei is now the biggest contender in the tri-folding segment, but Samsung may also join the race with a tri-fold version of its Galaxy Fold devices.
    • You can now measure internet speed and download videos using PowerToys Run by Taras Buria PowerToys Run is among my favorite modules, which I use daily (some of them should be integrated into Windows 11). This powerful utility is great for finding stuff, launching apps, navigating the web, and a lot more. Third-party modules help expand PowerToys Run's functionality and add additional capabilities like controlling Spotify, asking ChatGPT, and more. Now, there are three new modules you may find useful: speed test, video downloader, and vocabulary. The SpeedTest module uses Ookla Speedtest CLI for local execution without third-party tracking or ads. It has a modern, theme-aware user interface, and runs with a single command: just open Run and type spt to measure your internet connection speed. The result will show up in a new window with the ability to copy the result URL. The module also supports x64 and ARM systems. The VideoDownloader plugin lets you download videos from YouTube and other websites. You can specify the video quality and format (audio-only, for example) and select where to save the video. To make it work, open PowerToys Run, type dl and add a video URL. Finally, the Definition plugin from the same developer works as a powerful vocabulary that offers word definitions, word pronunciations, phonetics and synonyms, usage examples, and more. Note that these modules are not available in PowerToys out of the box. You need to download them from GitHub and install them manually. Here is how to do that: Download SpeedTest, VideoDownloader, or Definition plugins from their GitHub repositories. Extract downloaded plugins into %LOCALAPPDATA%\Microsoft\PowerToys\PowerToys Run\Plugins\ Open PowerToys Run (Alt + Space is the default shortcut) and launch plugins using their corresponding shortcuts (spt, dl, or def, all three can be customized in settings). You can also configure plugins in PowerToys Run settings. You can find more third-party modules for PowerToys Run on GitHub.
    • Showing people how to self host their own media is harmful, according to YouTube by David Uzondu YouTube has taken down a video from tech creator Jeff Geerling that demonstrated how to use LibreELEC, a lightweight operating system for turning devices into media centers, on a Raspberry Pi 5 for 4K video playback. The video, titled "I replaced my Apple TV—with a Raspberry Pi", originally published in May 2024, was removed in June 2025 under YouTube's "Harmful or dangerous content" policy. According to the violation notice, YouTube claimed the video showed "how to get unauthorized or free access to audio or audiovisual content, software, subscription services, or games that usually require payment." Image via Jeff Geerling Geerling strongly refuted YouTube's claims. He stated clearly, "I purposefully avoid demonstrating any of the tools that are popularly used to circumvent purchasing movie, TV, and other media content." He also emphasized that his own Network Attached Storage, or NAS, contains only legally acquired content. This isn't Geerling's first run-in with YouTube over self-hosted media tools. Last October, his tutorial titled "Better than Disney+: Jellyfin on my NAS" was hit with a similar strike for showing how to set up Jellyfin, an open source media server for organizing and streaming personal media. That strike was quickly overturned after an appeal. But this time, YouTube rejected his appeal, even though the LibreELEC video had been live for over a year, had racked up over half a million views, and contained no promotion of anything illegal. This whole thing feels a lot like what happened with youtube-dl. It's a simple command-line tool for downloading videos, used by tons of people for perfectly legal reasons like saving public domain content or backing up their own uploads. But that didn't stop the RIAA from hitting it with a DMCA takedown on GitHub, calling it a piracy tool. The community pushed back hard, and eventually it was brought back, thanks in part to support from groups like the Electronic Frontier Foundation who pointed out that not everything that can be misused is automatically bad. Side note, the youtube-dl project appears to be unmaintained (the last release was in 2021), if you're looking for an alternative, consider its very popular fork, yt-dlp. After the appeal was rejected, YouTube required Geerling to complete "policy training" to avoid a more serious, permanent strike on his channel. He eventually gave in and took the training. Anyways, if you're interested, he has uploaded the removed LibreELEC video to Internet Archive for anyone to watch.
    • Thanks to Herr Musk being a total poison pill, they can't even give those pieces of scrap away.  They can't even ship them to the UK/EU because they're completely illegal over here.  
  • Recent Achievements

    • 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
    • Week One Done
      jfam earned a badge
      Week One Done
    • First Post
      survivor303 earned a badge
      First Post
  • Popular Contributors

    1. 1
      +primortal
      438
    2. 2
      +FloatingFatMan
      244
    3. 3
      snowy owl
      223
    4. 4
      ATLien_0
      212
    5. 5
      Xenon
      152
  • Tell a friend

    Love Neowin? Tell a friend!