• 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

    • NTLite 2025.06.10459 is out.
    • Wireshark 4.4.7 by Razvan Serea  Wireshark is a network packet analyzer. A network packet analyzer will try to capture network packets and tries to display that packet data as detailed as possible. You could think of a network packet analyzer as a measuring device used to examine what's going on inside a network cable, just like a voltmeter is used by an electrician to examine what's going on inside an electric cable (but at a higher level, of course). In the past, such tools were either very expensive, proprietary, or both. However, with the advent of Wireshark, all that has changed. Wireshark is perhaps one of the best open source packet analyzers available today. Deep inspection of hundreds of protocols, with more being added all the time Live capture and offline analysis Standard three-pane packet browser Multi-platform: Runs on Windows, Linux, OS X, Solaris, FreeBSD, NetBSD, and many others Captured network data can be browsed via a GUI, or via the TTY-mode TShark utility The most powerful display filters in the industry Rich VoIP analysis Read/write many different capture file formats Capture files compressed with gzip can be decompressed on the fly Live data can be read from Ethernet, IEEE 802.11, PPP/HDLC, ATM, Bluetooth, USB, Token Ring, Frame Relay, FDDI, and others (depending on your platfrom) Decryption support for many protocols, including IPsec, ISAKMP, Kerberos, SNMPv3, SSL/TLS, WEP, and WPA/WPA2 Coloring rules can be applied to the packet list for quick, intuitive analysis Output can be exported to XML, PostScript®, CSV, or plain text Wireshark 4.4.7 changelog: The following vulnerabilities have been fixed wnpa-sec-2025-02 Dissection engine crash. Issue 20509. CVE-2025-5601. The following bugs have been fixed Wireshark does not correctly decode LIN "go to sleep" in TECMP and CMP. Issue 20463. Dissector bug, Protocol CIGI. Issue 20496. Green power packets are not dissected when proto_version == ZBEE_VERSION_GREEN_POWER. Issue 20497. Packet diagrams misalign or drop bitfields. Issue 20507. Corruption when setting heuristic dissector table UI name from Lua. Issue 20523. LDAP dissector incorrectly displays filters with singleton "&" Issue 20527. WebSocket per-message compression extentions: fail to decompress server messages (from the 2nd) due to parameter handling. Issue 20531. The LL_PERIODIC_SYNC_WR_IND packet is not properly dissected (packet-btle.c) Issue 20554. Updated Protocol Support AT, BT LE LL, CIGI, genl, LDAP, LIN, Logcat Text, net_dm, netfilter, nvme, SSH, TCPCL, TLS, WebSocket, ZigBee, and ZigBee ZCL Download: Wireshark 4.4.7 | 83.2 MB (Open Source) Download: Portable Wireshark 4.4.7 | ARM64 Installer View: Wireshark Website | Screenshot Get alerted to all of our Software updates on Twitter at @NeowinSoftware
    • Snapchat finally has a watchOS app, a decade after the Apple Watch launched by David Uzondu Snap has announced that Snapchat is finally hopping onto Apple Watch, something many users have probably been waiting for. This new app lets you easily preview an incoming message right on your wrist and then fire back a reply without ever needing to grab your iPhone. For those quick responses, you have options: you can tap out a message on the keyboard, use Scribble to draw letters, dictate your reply, or just send a fitting emoji. Snap says it's trying to make Snapchat easier to use on all the different devices people have in their lives. It's already seen people using Snapchat on tablets and the web, so bringing it to wearables like the Apple Watch feels like the next natural move. That marks a big change from back in 2015 when the Apple Watch first launched. At the time, Snap took a more cautious "wait and see" approach, wanting to see if people actually used smartwatches before building an app. New app launches are not always perfect. It is still early days for the watchOS app, as some users on Reddit have reported the app being stuck on the loading screen. Hopefully, Snap will address these initial teething problems quickly. This expansion to Apple Watch comes after the company abandoned its widely criticized three-tab app redesign following a notable drop in its North American daily active users and significant negative feedback. That redesign, introduced back in September 2024, was meant to simplify things but ended up frustrating many, leading Snap to reverse course after about seven months and work on a refined five-tab layout. Meanwhile, Android smartwatch users with Wear OS are still in a different boat, as there is no official, dedicated Snapchat app for that platform yet. They can typically only receive notifications, and attempts to sideload the full Android app often result in a clunky experience.
    • I've asked Sayan to limit these articles to science tech news.
    • LeafView 3.6.4 by Razvan Serea LeafView is a fast, open-source image viewer built with Electron. It offers a sleek, minimal UI for fast and efficient image browsing. Supporting various formats, LeafView ensures a smooth viewing experience with essential features like zoom, rotation, and slideshow mode. Designed for simplicity and performance, it utilizes hardware acceleration for smooth rendering and supports touch gestures for seamless navigation. LeafView key features: Lightweight & Open-Source – Minimal resource usage with a clean, efficient design Electron-Based – Cross-platform compatibility with modern UI Multiple Image Format Support – Opens JPG, PNG, GIF, BMP, and more Smooth Rendering – Hardware acceleration for fast performance Essential Image Controls – Zoom, rotate, and slideshow mode Touch Gesture Support – Seamless navigation on compatible devices Minimal UI – Focused on simplicity and ease of use LeafView 3.6.4 changelog: Update electron to v36.4.0 Download: LeafView 3.6.4 | Portable | ~100.0 MB (Open Source) View: LeafView Website | Other operating systems | Screenshot Get alerted to all of our Software updates on Twitter at @NeowinSoftware
  • Recent Achievements

    • One Year In
      survivor303 earned a badge
      One Year In
    • Week One Done
      jbatch earned a badge
      Week One Done
    • First Post
      Yianis earned a badge
      First Post
    • Rookie
      GTRoberts went up a rank
      Rookie
    • First Post
      James courage Tabla earned a badge
      First Post
  • Popular Contributors

    1. 1
      +primortal
      419
    2. 2
      +FloatingFatMan
      182
    3. 3
      snowy owl
      181
    4. 4
      ATLien_0
      174
    5. 5
      Xenon
      137
  • Tell a friend

    Love Neowin? Tell a friend!