So I'm having that class in my university where we do all kind of sorts, now we make recursive sorting, aka quickSort. Where ok you all know what it does , split the array to two parts and so on till it ends with 1 element and then sort them.
So we ware discussing which one would be faster and why this is so called quicksort, it ends up that the complexity of the quickSort is n.log2(n), while for example bubble sort is n^2. Ok so I wrote the bouth codes in c# and using the stopwatch of c# i calcualte hte ms to execute bouth alogirithyms , where I generate random numbers between -65000,65000 and array with lenght 50 000 elements.
So bubblesort did the sorting for first time 23 seconds second time 29(cause they are randoms ..) , even if i make an array with 50k elements with first elements n-i. Aka it would need to sort everything , it does it for 27 sec(so close the the random) if i make an array starting from i , it does need 17 sec to sort it.
So I ran the quickSort , and well has passed 5 minutes and still no result... if i run it with arra[i] = i; or n-i; it gives me stackoverflow exception.
The only place where qSort is faster is when have an array with elements like 100 or 200 and they are already sorted ( aka array[i]=i) and its faster with like 0.1-0.2 sec. Where buble sort can sort really huge arrays while qSort gives me stackoverflow.
So back to complexity , qSort for 50 000 elements = 780482 while bublesort = 2 500 000 000 Its clear as bright day qSort need to be what? 99.99% faster. But its not? Why im really curious about this , since my Lector had say that qSort is a lot faster. But after all kind of test its seems to be a (slighty) faster compare to bubblesort and its working only with array with not so much elements.(10k randoms elements qSort 17 sec while bublesort 7).
My pc is with i7 4cores each on 2.6 ghz, and I have 16 gb RAM DDR4.
I will be happy if someone clear the things , since my lector seems to give me a false information.
EDIT bouth codes: qsort..................................
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace QuickSort
{
class QuickSort
{
static public int Partition(int[] numbers, int left, int right)
{
int pivot = numbers[left];
while (true)
{
while (numbers[left] < pivot)
left++;
while (numbers[right] > pivot)
right--;
if (left < right)
{
int temp = numbers[right];
numbers[right] = numbers[left];
numbers[left] = temp;
}
else
{
return right;
}
}
}
static public void SortQuick(int[] arr, int left, int right)
{
// For Recusrion
if (left < right)
{
int pivot = Partition(arr, left, right);
if (pivot > 1)
SortQuick(arr, left, pivot - 1);
if (pivot + 1 < right)
SortQuick(arr, pivot + 1, right);
}
}
static void Main(string[] args)
{
var watch = System.Diagnostics.Stopwatch.StartNew();
Random rnd = new Random();
int max = Convert.ToInt32(Console.ReadLine());
int[] numbers = new int[max];
for (int i = 0; i < max; i++)
{
numbers[i] = rnd.Next(-65000, 65000);
}
// the code that you want to measure comes here
SortQuick(numbers, 0, max - 1);
for (int i = 0; i < max; i++)
Console.WriteLine(numbers[i]);
watch.Stop();
var elapsedMs = watch.ElapsedMilliseconds;
Console.WriteLine(elapsedMs);
Console.ReadLine();
}
}
}
Bublesort................................
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace bublesort
{
class Program
{
static void Main(string[] args)
{
var watch = System.Diagnostics.Stopwatch.StartNew();
// the code that you want to measure comes here
int n = int.Parse(Console.ReadLine());
int[] arr = new int[n];
Random rnd = new Random();
int temp = 0;
for (int i = 0; i < n; i++)
{
arr[i] = rnd.Next(-65000,65000);
}
for (int write = 0; write < arr.Length; write++)
{
for (int sort = 0; sort < arr.Length - 1; sort++)
{
if (arr[sort] > arr[sort + 1])
{
temp = arr[sort + 1];
arr[sort + 1] = arr[sort];
arr[sort] = temp;
}
}
}
for (int i = 0; i < arr.Length; i++)
Console.WriteLine(arr[i]);
watch.Stop();
var elapsedMs = watch.ElapsedMilliseconds;
Console.WriteLine(elapsedMs);
}
}
}
If you have duplicates in your array, it will happen that the two while-loops end with array [left] = array [right] = pivot. The swap does nothing, and since you don't increase left and decrease right, your quicksort will be stuck forever.
Try with an array of length 2 and two equal elements. It will hang immediately.
Also, by choosing array [left] as the pivot, you guarantee worst case (quadratic) behaviour for sorted arrays once that bug is fixed.