Чтобы не изобретать велосипед я просто воспользовался готовыми алгоритмами (перевел с Си на 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 - на практике не применяются ("ну зачем тогда их упоминать? так, для галочки что-ли?"). |