• 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

    • Arc 1.57.0 by Razvan Serea ARC browser is finally here for Windows, bringing its unique and modern approach to browsing. With a clean interface and a powerful sidebar, ARC makes managing tabs and organizing your workflow a breeze. You can group tabs, pin important pages, and quickly switch between work and personal spaces without clutter. It’s designed to be fast, customizable, and genuinely useful, making it more than just a browser—it’s a productivity tool. If you’re on Windows and want a fresh way to browse and stay organized, ARC is worth checking out. ARC browser key features: Split View: Work with multiple tabs side by side in a single window for efficient multitasking. Tab Grouping: Organize tabs into customizable groups for better workflow management. Pinned Tabs: Keep essential pages permanently accessible in the sidebar. Spaces: Create separate workspaces for different projects or personal use, reducing clutter. Sidebar Integration: Access bookmarks, notes, and tools directly from the sidebar for quick navigation. Customizable Themes: Personalize the browser’s appearance with themes and color schemes. Quick Search: Find tabs, history, or bookmarks instantly with a powerful search bar. Lightning-Fast Performance: Built for speed with optimized resource usage and minimal lag. Built-in Note-Taking: Jot down ideas or save snippets directly within the browser. Focus Mode: Hide distractions and focus on a single tab or task. Cross-Device Syncing: Seamlessly sync your data across multiple devices for a unified experience. Keyboard Shortcuts: Boost productivity with customizable shortcuts for common actions. AI-Powered Suggestions: Get smart recommendations for tabs, bookmarks, and workflows. Privacy Controls: Built-in tools for blocking trackers and managing cookies for enhanced security. Extensions Support: Compatible with popular browser extensions to extend functionality. Arc Browser 1.57.0 release notes: ''Thanks as always for using Arc. This week's release includes a bump to Chromium 137.0.7151.69, which patched three security vulnerabilities. Enjoy!'' Download: Arc Browser 1.57.0 | 1.9 MB (Freeware) View: Arc Browser Website | Screenshot Get alerted to all of our Software updates on Twitter at @NeowinSoftware
    • they put useless AI, new plastick sticker 8K and price +$80 for nothing
    • this AD block popup in annoying
  • Recent Achievements

    • 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
    • Week One Done
      CHUNWEI earned a badge
      Week One Done
  • Popular Contributors

    1. 1
      +primortal
      427
    2. 2
      +FloatingFatMan
      237
    3. 3
      ATLien_0
      213
    4. 4
      snowy owl
      207
    5. 5
      Xenon
      159
  • Tell a friend

    Love Neowin? Tell a friend!