Почему quickSort медленнее, чем bubblesort?

Question

Итак, у меня есть класс в моем университете, где мы делаем все виды, теперь мы делаем рекурсивную сортировку, а также quickSort. Где хорошо, вы все знаете, что он делает, разделите массив на две части и так далее, пока он не закончится с 1 элементом, а затем отсортируйте их.

Итак, мы обсуждаем, какой из них будет быстрее, и почему это так называется quicksort, и заканчивается тем, что сложность quickSort равна n.log2 (n), тогда как, например, сортировка пузырьков n^2. Хорошо, поэтому я написал коды bouth в C# и используя секундомер C# i calcualte hte ms для выполнения алоритимов bouth, где я генерирую случайные числа между -65000, 65000 и массивом с длиной 50 000 элементов.

Так что bubblesort сделал сортировку в первый раз 23 секунды второй раз 29 (потому что они являются randoms ..), даже если я делаю массив с 50k элементами с первыми элементами n-i. Ака ему нужно будет все сортировать, он делает это в течение 27 секунд (так близко к случайному), если я создаю массив, начиная с i, ему нужно 17 секунд, чтобы отсортировать его.

Итак, я запустил quickSort, и хорошо прошло 5 минут, и все еще нет результата ... если я запустил его с помощью arra [i] = i; или n-i; это дает исключение stackoverflow.

Единственное место, где qSort быстрее, - это массив с элементами типа 100 или 200, и они уже отсортированы (aka array [i] = i) и быстрее, чем 0,1-0,2 с. Где сортировка buble может сортировать действительно огромные массивы, в то время как qSort дает мне stackoverflow.

Итак, к сложности, qSort для 50 000 элементов = 780482 while bublesort = 2 500 000 000 Его ясный, как яркий день qSort должно быть чем? На 99,99% быстрее. Но это не так? Почему им действительно интересно об этом, так как мой Лектор сказал, что qSort намного быстрее. Но после всего своего теста его, кажется, (немного) быстрее сравнивают с bubblesort и его работают только с массивом с не большим количеством элементов. (10k randoms элементов qSort 17 секунд, в то время как bublesort 7).

Мой компьютер с i7 4cores каждый на 2,6 ГГц, и у меня 16 ГБ оперативной памяти DDR4.

Буду рад, если кто-то очистит все, так как мой лектор, кажется, дает мне ложную информацию.

EDIT коды: обе 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); 
    } 
} 
} 

Answer 1

Если у вас есть дубликаты в массив, то произойдет, что два цикла while заканчиваются массивом [left] = array [right] = pivot. Сделка ничего не делает, и поскольку вы не увеличиваете левый и не уменьшаетесь вправо, ваш quicksort будет застрял навсегда.

Попробуйте массив длиной 2 и два равных элемента. Он будет висеть немедленно.

Кроме того, выбирая в качестве стержня массив [left], вы гарантируете наихудшее (квадратичное) поведение для отсортированных массивов после исправления ошибки.

Answer 2

static public void Quicksort(int[] numbers, int left, int right) 
    { 
     int i = left, j = right; 
     int pivot = numbers[(left+right)/2]; 

     while (i <= j) 
     { 
      while (numbers[i] < pivot) 
      { 
       i++; 
      } 

      while (numbers[j] > pivot) 
      { 
       j--; 
      } 

      if (i <=j) 
      { 
       // Swap 
       int tmp = numbers[i]; 
       numbers[i] = numbers[j]; 
       numbers[j] = tmp; 

       i++; 
       j--; 
      } 

     } 

     // Recursive calls 
     if (left < j) 
     { 
      Quicksort(numbers, left, j); 
     } 

     if (i < right) 
     { 
      Quicksort(numbers, i, right); 
     } 
    } 

проблема Да решить для guidence THX, когда я сделал стержень среднего элемента, Im, в настоящее время сортировки 100 000 случайных элементов в интервале [-65000 до 65000] в течение 8 сек. В то время как для сортировки buble требуется 71 сек. Или Q сортировка на 90% быстрее, чем пузырь;;).