Собственно у меня такой вопрос: здесь http://forum.vingrad.ru/index.php?showforum=13 описаны алгоритмы сортировки массивов. Какой самый предпочтительный, исходя из того, что требуется что-то одно -

1) или высокая скорость (но памяти можно тратить много),

либо наоборот:

2) скорость не ахти какая, но зато памяти расходуестя совсем немного.

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

Timer1 имеет interval = 100

Label1, Label2 - время начала и конца сортировки соответственно.

Label3 - декорация с надписью "Число элементов в массиве:"

Text2.Text - укажем число элементов массива

Command1, Command2 - сортировка методом пузырька и сортировка методом простого выбора соответственно.

Код

Option Explicit Private ValMin As Integer Private ValSec As Integer Private Sub Command1_Click() ' сортировка методом пузырька On Error Resume Next Kill "c:\Experiment" Kill "c:\Experiment_temp" Dim Count As Long Dim rand As String Dim i As Long i = Val(Text2.Text) Count = i ' Это для отладки ' Сделаем случайный выбор чисел Do Randomize ' Улучшает рандомизатор - можно и без него, но тогда будут повторы. rand = rand & Left(Rnd * 10 * 0.0325436, 7) & vbCrLf i = i - 1 Loop While i > 0 Open "c:\Experiment" For Append As #1 Print #1, rand Close ' сортировка ValMin = Minute(Time) ' запишем реальное время начала сортировки ValSec = Second(Time) Dim a() As String Dim swap As String Dim m As Long Dim buffer As String         ' буфер, где хранится весь считанный файл Dim current_string As String ' буфер для хранения текущей считанной строки ' NumberLine служит одновременно и счетчиком строк в цикле do while ... loop ReDim a(0 To NumberLine("c:\Experiment")) As String For i = 0 To NumberLine("c:\Experiment")     Open "c:\Experiment" For Input As #1                  Do While Not EOF(1)  ' EOF(1) - конец файла 1 (FileNumber),                              ' т.е. будет происходить чтение                              ' всего файла         Line Input #1, current_string           buffer = buffer + current_string + vbCrLf a(i) = current_string i = i + 1                  Loop     Close #1 Next i Label1.Caption = Time ' здесь начинается сортировка методом пузырька: m = NumberLine("c:\Experiment") Do     For i = 0 To m - 1         If a(i) > a(i + 1) Then             swap = a(i)             a(i) = a(i + 1)             a(i + 1) = swap         End If     Next i     m = m - 1 Loop While m > 0 ' здесь получим число секунд, которое требуется на сортировку массива: 'MsgBox Minute(Time) - ValMin & " минут ушло на сортировку" 'MsgBox Second(Time) - ValSec & " секунд ушло на сортировку" Label2.Caption = Time MsgBox (Minute(Time) - ValMin) * 60 + (Second(Time) - ValSec) _ & " секунд(ы) ушло на сортировку" & vbNewLine _ & " массива, состоящего из " & Count & " элементов" ' Запишем отстортированный массив в файл: Dim Line As Long Line = NumberLine("c:\Experiment") Open "c:\Experiment_temp" For Append As #1 ' сохраним во временный файл массив, отсортированный по алфавиту     For i = 0 To Line     Print #1, a(i)     Next i Close #1 End Sub Private Function NumberLine(FileName As String) As Long Dim buffer As String            Dim current_string As String    If Dir(FileName) <> "" Then         Open FileName For Input As #1                  Do While Not EOF(1)  ' EOF(1) - конец файла 1 (FileNumber),                              ' т.е. будет происходить чтение                              ' всего файла         Line Input #1, current_string          buffer = buffer + current_string + vbCrLf         NumberLine = NumberLine + 1        Loop          Close #1 Else: MsgBox "Файл не существует" & vbNewLine & "или имя файла указано неверно", vbCritical, "Ошибка" End If End Function Private Sub Command2_Click() ' сортировка методом простого выбора On Error Resume Next Kill "c:\Experiment" Kill "c:\Experiment_temp" Dim rand As String Dim Count As Long Dim i As Long i = Val(Text2.Text) Count = i ' Это для отладки Do Randomize rand = rand & Left(Rnd * 10 * 0.0325436, 7) & vbCrLf i = i - 1 Loop While i > 0 Open "c:\Experiment" For Append As #1 Print #1, rand Close ValMin = Minute(Time) ' запишем реальное время начала сортировки ValSec = Second(Time) Dim a() As String Dim swap As String Dim buffer As String         ' буфер, где хранится весь считанный файл Dim current_string As String ' буфер для хранения текущей считанной строки ' NumberLine служит одновременно и счетчиком строк в цикле do while ... loop ReDim a(0 To NumberLine("c:\Experiment")) As String For i = 0 To NumberLine("c:\Experiment")     Open "c:\Experiment" For Input As #1                   Do While Not EOF(1)  ' EOF(1) - конец файла 1 (FileNumber),                              ' т.е. будет происходить чтение                              ' всего файла         Line Input #1, current_string             buffer = buffer + current_string + vbCrLf a(i) = current_string i = i + 1                   Loop     Close #1   Next i ' Здесь начинается сортировка методом простого выбора: Dim N As Long Dim min As Single ' smallest element in array Dim index As Long ' index of the smallest element in array Dim l As Long, j As Long N = NumberLine("c:\Experiment") Label1.Caption = Time ' Сортировка методом простого выбора: For l = 0 To N - 1 min = a(l) index = l          For j = l + 1 To N         If a(j) < min Then            min = a(j)            index = j         End If     Next j          swap = a(index)     a(index) = a(l)     a(l) = swap      Next l ' здесь получим число секунд, которое требуется на сортировку массива: Label2.Caption = Time MsgBox (Minute(Time) - ValMin) * 60 + (Second(Time) - ValSec) _ & " секунд(ы) ушло на сортировку" & vbNewLine _ & " массива, состоящего из " & Count & " элементов" ' Запишем отстортированный массив в файл: Dim Line As Long Line = NumberLine("c:\Experiment") Open "c:\Experiment_temp" For Append As #1 ' сохраним временный файл, отсортированный по алфавиту     For l = 0 To Line     Print #1, a(l)     Next l Close #1 End Sub Private Sub Form_Load() Timer1.Enabled = True End Sub Private Sub Form_QueryUnload(Cancel As Integer, UnloadMode As Integer) On Error Resume Next Kill "c:\Experiment" Kill "c:\Experiment_temp" End Sub

Что лучше? Если надо сортировнуть 100 000, 200 000 элементов?

Мне попадалась программа, которая в красках показывает результаты работы различных алгоритмов. Поищи, может найдешь у нас на форуме, но я не смог ее найти...
А вообще посмотри статью про ассемблер и воспользуйся этими знаниями после того, как выберешь алгоритм. А еще лучше найди готовый алгоритм на асме и постарайся заделать его в свою прогу. Думаю прирост скорости будет солидный.
[off]Ну и подпись у тебя. [/off]

(2)насколько я знаю, быстрая сортировка не использует дополнительной памяти (если не считать какого-то конечного числа ячеек, не зависящего от длины массива), но она не всегда дает время пропорциональное n*log n (зависит от удачного выбора разделяющего элемента)
(1)есть сортировка слиянием, она гарантирует n*log n, но использует дополнительно столько же памяти, сколько нужно для хранения самого массива...

- если 99% списка уже отсортировано используем пузырьковую сортировку;
- если список мал - сортировка выбором;
- если значения находятся в связанном списке - блочная сортировка на основе связанного списка;
- если элементы в списке - целые числа, разброс значений к-рых невелик (до нескольких тыс.) - сортировка подсчетом;
- если значения лежат в широком диапазоне и не являются целыми числами - блочная сортировка на основе массива;
- если не можем тратить доп. память, к-рая требуется для блочной сортировки, исп-ем быструю сортировку.

для больших списков можно пользовать пирамидальную или сортировку слиянием (работают медленнее быстрой сорт-ки).
пузырек хорош для почти отсортированных списков, больше нигде ;)
быстрая сортировка приводит к проблемам при большом кол-ве одинаковых значений.

http://algolist.manual.ru/sort/faq/q12.php

Чтобы не изобретать велосипед я просто воспользовался готовыми алгоритмами (перевел с Си на VB).

Код

////////////////////////////////////////////////////////////////////////////// // //  Exchanges (array sorting) //  (б) Johna Smith, 1996 // //  Method description: //    Using linear search find smallest i with the following property: //    a(i)>a(i+1), swap a(i) and a(i+1) and repeat this process searching //    from a(i+1). After one pass greatest number will be placed at right //    place. We'll decrease amount of acting elements on each pass. //    When 2 elements will left we'll say that array is sorted // ////////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <conio.h> // getch() - чтобы сразу не вылетало :) const N=     10;  // number of array elements int array[N]={100,15,234,11,63,78,4,200,0,4}; int swp; // auxulary variable for swapping int m; // number of active elements on current pass void show_array(void) // this function prints array {  for (int i=0;i<N;i++)    printf("%d ",array[i]); } void main(void) {   // Printing unsorted array   printf("Unsorted array: ");   show_array();   // Sorting   m=N; // All elements acting at first pass   while (m>1) // repeat passes while there is more than one element   {     for (int i=0;i<m-1;i++) // main loop     {       // searching for smallest element       if (array[i]>array[i+1]) // if a(i)>a(i+1)       {         // swapping a(i) and a(i+1)         swp=array[i];         array[i]=array[i+1];         array[i+1]=swp;       }     }     m--; // decreasing amount of acting elements   }   // Printing sorted array   printf("\nSorted array: ");   show_array(); getch() }

Код

////////////////////////////////////////////////////////////////////////////// // //  Straight selections (array sorting) //  (б) Johna Smith, 1996 // //  Method description: //    searching for smallest element in array, swapping with first element, //    repeat this operation starting search from second element and so on //    array become sorted when we'll start search from (n-1)-th element // ////////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <conio.h> const N = 10;  // number of elements in array int array[N]={100,15,234,11,63,78,4,200,0,4}; int min; // smallest element in array int index; // index of the smallest element in array int swp; // auxulary variable for swapping void show_array(void) // this function prints array {  for (int i=0;i<N;i++)    printf("%d ",array[i]); } void main(void) {   // Printing unsorted array   printf("Unsorted array: ");   show_array();   // Sorting   for (int i=0;i<N-1;i++) // main loop   {     // searching for smallest element from i-th     min=array[i]; // setting i-th elementas smallest     index=i;     for (int j=i+1;j<N;j++)       if (array[j]<min)  // if there is element less than smallest       {          min=array[j];  // then remember its value          index=j;       // and index       }     // swapping i-th and smallest element     swp=array[index];     array[index]=array[i];     array[i]=swp;   }   // Printing sorted array   printf("\nSorted array: ");   show_array(); getch() }

Конечно, на этих примерах, где сортируются всего-то 10 элементов разницы я не увижу. Даже 1000 элементов - разница заметна с трудом на машинах, на которых я работаю. Может действительно лучше на Си написать, когда задача того стоИт.

А вообще овчинка не стоит выделки - в среднем: 512 мб памяти и процессоры 2,4 Гц Xeon/Pentium/Celeron

Цитата(__Sergey__ @ 21.9.2005, 01:04)

пузырек хорош для почти отсортированных списков, больше нигде ;)

так что будем пузырьками мучать машины, а то стыдно как-то - загрузка 2-3 % . Я же ведь с испугу, что несколько часов уходит на сортировку (массивов внушительных размеров) - читая книги, которым > 10 лет.

Akina, хорошая статья.

Ну, а по поводу этих 2-ух сортировок, что можете сказать?

Код

////////////////////////////////////////////////////////////////////////////// // //  Quick sort (recursive) //  (c) Johna Smith, 1996 // //  Method description: //    1) Split array into two parts and remember middle element //    2) Scan left part for element greater than middle //    3) Scan right part for element less than middle //    4) Swap these elements //    So we have an array where all left elements are less than right elements //    Apply these four steps to each part (left and right) of the array //    until we have parts that contain only one element. // ////////////////////////////////////////////////////////////////////////////// #include <stdio.h> const N=     10;  // array size int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers void show_array(void) // this function displays array {  for (int i=0;i<N;i++)    printf("%d ",array[i]); } void sort(int left,int right) {  int i,j;  int element; // auxulary variable for middle element in the interval  int swp; // auxulary variable for swapping  i=left;  // index for left part  j=right;  // index for right part  element=array[(left+right)/2]; // middle element  do  {    while (array[i]<element) i++; // scanning left part    while (element<array[j]) j--; // scanning right part    if (i<=j)    {      // swapping elements      swp=array[i];      array[i]=array[j];      array[j]=swp;      i++; j--;    }  } while (i<=j);  if (left<j) sort(left,j); // applying the same procedure to the left part  if (i<right) sort(i,right); // applying the same procedure to the right part } void main(void) {  // Displaying unsorted array  printf("Unsorted array: ");  show_array();  // Sorting  sort(0,N-1);  // Displaying sorted array  printf("\nSorted array: ");  show_array(); }

И эта:

Код

////////////////////////////////////////////////////////////////////////////// // //  Quick sort (non-recursive) //  (c) Johna Smith, 1996 // //  Method description: //    1) Split array into two parts and remember middle element //    2) Scan left part for element greater than middle //    3) Scan right part for element less than middle //    4) Swap these elements //    So we have an array where all left elements are less than right elements //    Apply these four steps to each part (left and right) of the array //    until we have parts that contain only one element. // ////////////////////////////////////////////////////////////////////////////// #include <stdio.h> const N = 10;         // array size const STACK_SIZE = 4; // stack size must be >=log N int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers void show_array(void) // this function displays array {  for (int i=0;i<N;i++)    printf("%d ",array[i]); } struct {int left; int right;} stack[STACK_SIZE]; // stack emulation unsigned int ss; // current stack size int i,j; int element; // auxulary variable for middle element in the interval int swp; // auxulary variable for swapping int left,right; // interval bounds void main(void) {  // Displaying unsorted array  printf("Unsorted array: ");  show_array();  // Sorting  ss=1;  stack[0].left=0;  stack[0].right=N-1;  do  {    // pushing from stack last request    left=stack[ss-1].left;    right=stack[ss-1].right;    ss--;    do    {      // splitting array[left]..array[right] interval      i=left;  // index for left part      j=right;  // index for right part      element=array[(left+right)/2]; // middle element      do      {        while (array[i]<element) i++; // scanning left part        while (element<array[j]) j--; // scanning right part        if (i<=j)        {          // swapping elements          swp=array[i];          array[i]=array[j];          array[j]=swp;          i++; j--;        }      } while (i<=j);      // pushing request into stack      // (we select longest part and push request for it to reduce stack size)      if (j-left<right-i)      {        if (i<right) // push request for the right part (because it's longer than left)        {          ss++;          stack[ss-1].left=i;          stack[ss-1].right=right;        }        right=j; // continue sorting left part      } else      {        if (left<j) // push request for the left part (because it's longer than right)        {          ss++;          stack[ss-1].left=left;          stack[ss-1].right=j;        }        left=i; // continue sorting right part      }    } while(left<right);  } while(ss!=0);  // Displaying sorted array  printf("\nSorted array: ");  show_array(); }

Там еще есть Shell-сортировка (что за сортировка? с англ - "оболочка"). И бинарная.
Извините, что пришлось так много приводить кода на Си, но особого труда перевести на VB не составит, если вспомнить синтаксис Си.

И еще последний вопрос - на http://algolist.manual.ru/sort/faq/q12.php говорится о том, что SelectSort, BubbleSort, ShellSort - на практике не применяются ("ну зачем тогда их упоминать? так, для галочки что-ли?").

Цитата(Voldemar2004 @ 21.9.2005, 19:51)

("ну зачем тогда их упоминать? так, для галочки что-ли?").

Ну в том числе и для галочки... а вообще - они максимально просты в программной реализации, пишутся "на лету" - при отсутствии готового кода можно временно в тест-целях использовать их... или использовать их для сравнительных тестов.