Сортировка букв английского алфавита (С/C++)

[saturn404]

Помогите пожалуйста решить задачку. Быстрая сортировка букв английского алфавита, если последовательность менее 6 элементов методом прямых включений. Буквы будут вводиться с клавиатуры.
Не знаю с чего начать, подскажите в каком направлении двигаться.

[OptikLab]

Заранее извиняюсь за флуд...
Эммс....если (длина < 6) тогда сортируем включениями если нет - быстрой.
Пример включений:

Код: Выделить всё

void insertionsort(ap::real_1d_array& arr, int n)
{
    int i;
    int j;
    int k;
    double tmp;

    n = n-1;
    i = 1;
    do
    {
        j = 0;
        do
        {
            if( arr(i)<=arr(j) )
            {
                k = i;
                tmp = arr(i);
                do
                {
                    arr(k) = arr(k-1);
                    k = k-1;
                }
                while(k>j);
                arr(j) = tmp;
                j = i;
            }
            else
            {
                j = j+1;
            }
        }
        while(j<i);
        i = i+1;
    }
    while(i<=n);
}


Пример быстрой:

const int N=100;

int main()
{
	srand( (unsigned)time( NULL ) );
	int nMas[N];
	//быстрая сортировка
	quickSort(nMas, 0, N);
	cout<<"\nQSort:"<<endl;
	for(int i=0; i<N;i++)
		cout<<nMas[i]<<" ";
	_getche();
	return 0;
}


int Partition(int* a, int lb, int ub)
{
	int t, pivot;
	int i, j, p;
	/* находим средний элемент и меняем его местами с первым */
	p = lb + ((ub - lb)>>1);
	pivot = a[p];
	a[p] = a[lb];
	/* сортируем массив в диапазоне lb+1..ub относительно среднего элемента pivot */
	i = lb+1;
	j = ub;
	while (1) 
			{
			while (i < j && pivot>a[i]) i++;
			while (j >= i && a[j]>pivot) j--;
			if (i >= j) 
				break;
			t = a[i];
			a[i] = a[j];
			a[j] = t;
			j--; 
			i++;
			}
	/* среднее значение находится в a[j] */
	a[lb] = a[j];
	a[j] = pivot;
	return j;
}


void quickSort(int *a, int lb, int ub)
{
	int m;
	while (lb < ub) 
			{
			/* На массиве из малого числа элементов быстрее сортирует метод Вставки*/
			if (ub - lb <= 12) 
				{
				insertSort(a, lb, ub);
				return;
				}
			/* находим номер элемента m, в котором лежит среднее зачение */
			m = Partition(a, lb, ub);
			/* сортируем меньшую часть, чтобы минимизировать требования стэка */
			if (m - lb <= ub - m) 
				{
				quickSort(a, lb, m - 1);
				lb = m + 1;
				} 
			else
				{
				quickSort(a, m + 1, ub);
				ub = m - 1;
				}
			}
}

void insertSort(int *a, int lb, int ub)
{
	int t;
	int i, j;

	for (i = lb + 1; i <= ub; i++)
		{
		t = a[i];
		/* Shift elements down until */
		/* insertion point found. */
		for (j = i-1; j >= lb && a[j]>t; j--)
			a[j+1] = a[j];
		/* insert */
		a[j+1] = t;
		}
}

[saturn404]

Спасибо. Сортировки я нашел, но соль не в том. Надо с чего то начать. Я думаю так: надо считать буквы в массив, затем присвоить каждой букве значение(a=1 b=2 c=3 d=4), эти значения отсортировать и уже уже отсортированные цифры присвоить буквам и вывести их на экран. Возможно, надо считывать коды клавиш через getch. Может есть какието еще варианты.... Вот.
Может я не прав, помогите кто чем может, 25-ого зачетная неделя.

[OptikLab]

Так а зачем присваивать порядок (1,2,3...), если в ASCII кодировке они уже упорядочены, только начинаются не с 1. Большие A-Z : коды 65 - 90, маленькие a-z : 97 - 122. Так вот ты считываешь все символы в массивчик, а потом упорядочиваешь в соответствии с кодом символа. Даже если введены символы в различном кейсе, большие буквы будут идти раньше маленьких.
--------------------------------------------------------------------------------
Добавлено сообщение
--------------------------------------------------------------------------------
Только причем тут тогда qsort, insertion_sort я не догнал =)

[saturn404]

Спасибо OptikLab, что поучавствовал. Я дошел до истины.

Код: Выделить всё

void main(){     clrscr(); char *I; int n,K,i,L,size,j;
printf("\nVvedite kolichestvo simvolov");
cin>>size;
I=new char[size];
printf("Vvedite elimenty\n");
for(j=0;j<size;j++)
{
 cin>>I[j];
 if(j<size)
 printf("Oshibka vvoda\n");
}

printf("\nSortirovka metodom pryamogo vklucheniya");
printf("\nIshodniy massiv");
for(n=0;n<j;n++)
printf("%2c",I[n]);
printf("\n");
for(i=1;i<j;i++)
{
 K=I[i];
 L=i;
 while(K<I[L-1])
{
 I[L]=I[L-1];
 L--;
}
I[L]=K;
}
 getch();
 printf("\n Otsartirovannyi massiv:\n");
 for(n=0;n<j;n++)
 printf("%2c",I[n]);
 printf("\n");
 getch();
 closegraph();
}           

Еще быструю прекручу и зачет