Самый быстрый вид сортировки массива

[Utkin]

Сообщение от Blade

Это метод "Пузырька", считается одним из самых медленных

Применительно к числам. Вообще скорость сортировки напрямую зависит не только от метода, но и сортируемых данных.

[rpy3uH]

Сообщение от Blade

Это метод "Пузырька", считается одним из самых медленных

может поспорим? что это не метод пузырька
в методе пузырька меняются местами соседние элементы до тех пор, пока весь массив не отсортируется
метод пузырька

repeat
 Flag := False;
 for i := 0 to n - 1 do
  if Arr [i] > Arr [i + 1] then begin 
   Temp := Arr [i]; 
    Arr [i] := Arr [i + 1];
    Arr [i + 1] := Temp; 
    Flag := True; 
   end; 
until Flag = False;

[Arigato]

Самый быстрый метод сортировки - линейная сортировка. Применительно к числам она очень эффективна, но требует давольно много ресурсов памяти.
При небольшой адаптации она применима и к строковым данным.

[Blade]

Сообщение от rpy3uH

может поспорим? что это не метод пузырька

Согласен, не метод пузырька
Зачем сразу спорить?

[ACE Valery]

Когда-то писала программу сравнения сортировок.
Массив заполнен числами от 0 до 999. Элементов в массиве - 500 000. Методы сортировки: пузырьком, вставками, выбором, рекурсивная(быстрая). По времени победила рекурсивная.

Может, и вам сравнить известные сортировки и опытным путем проверить, какая из них подходит именно к вашим данным.

[rpy3uH]

Сообщение от ACE Valery

Когда-то писала программу сравнения сортировок.

я тоже писал, лабораторная была такая в институте по исследованию методов сортировок

Сообщение от ACE Valery

Методы сортировки: пузырьком, вставками, выбором, рекурсивная(быстрая). По времени победила рекурсивная.

рекурсивная сортировка здесь лишняя, она не относится к простым методам и она не всегда подходит, так как всегда есть вероятность (хоть очень малая) что будет переполнение. И я не отрицаю что рекурсивная сортировка быстрая, я говорю: зачем извращаться, если можно сделать намного проще?

[pu4koff]

Можно еще сортировку шелла замутить

[Arigato]

Когда-то писала программу сравнения сортировок.
Массив заполнен числами от 0 до 999. Элементов в массиве - 500 000. Методы сортировки: пузырьком, вставками, выбором, рекурсивная(быстрая). По времени победила рекурсивная.

Решил замерить, сколько потребуется времени линейной сортировки для того, что бы отсортировать такой массив. Вот, набросал примерчик:

program Project1;

{$APPTYPE CONSOLE}

uses
  Windows;

const N = 500000;

var Mas: array[1..N] of Word;
    Data: array[0..999] of Integer;
    I: Integer;
    T: Cardinal;

procedure Sort1;
// Медленная сортировка:
var I, J: Integer;
    Tmp: Word;
begin
  for I := 1 to N - 1 do
    for J := I + 1 to N do
      if Mas[I] > Mas[J] then
      begin
        Tmp := Mas[I];
        Mas[I] := Mas[J];
        Mas[J] := Tmp;
      end; {if}
end; {proc Sort1}

procedure Sort2;
// Линейная сортировка массива:
var I, J, Idx: Integer;
begin
  FillChar (Data, SizeOf (Data), 0);
  for I := 1 to N do
    Inc (Data[Mas[I]]);
  Idx := 1;
  for I := 0 to 999 do
    for J := 1 to Data[I] do
    begin
      Mas[Idx] := I;
      Inc (Idx);
    end; {for}
end; {proc Sort2}

begin
  // НАЧАЛО: Заполняем массив
  Randomize;
  for I := 1 to N do
    Mas[I] := Random (1000);
  // КОНЕЦ: Заполняем массив
  T := GetTickCount;
  Sort2;
  WriteLn ('Time result (ms) = ', GetTickCount - T);
  ReadLn;
  for I := 1 to N do
    Write (Mas[I], ' ');
  ReadLn;
end.

Процедура Sort2 - линейная сортировка, Sort1 - для сравнения другой метод. Линейная сортировка справилась с данным массивом за 0 мс (мгновенно), Sort1 не хватило терпения дождаться окончания процесса.

[Levsha100]

Как уже было сказано ранее все зависит от исходных данных! А вообще и метод пузырька можно подогнать под свои цели, например вставить логическую переменку, и если на этой интерации не было перестановок-выйти из цикла, и тд!

[Utkin]

Полностью согласен. Обычные выкладки из учебников. Все дружно забыли что человека интереует опыт сортировки строковых данных, а не чисел. Данные по сортировке чисел, ИМХО, топикстартеру известны.