C ++ Quicksort Алфавитный массив
Я пытаюсь отсортировать массив алфавитов с помощью быстрой сортировки.
Я в основном пытался перейти от основного алгоритма и преобразовать его для работы с массивами символов.
Я думаю, что я почти там, но я просто не могу этого понять.
Буду признателен за любую оказанную помощь.
🙂
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int qscounter = 0;
int split(char a[], char low, char high)
{
char part_element = a[low];
for (;;) {
while (low < high && part_element <= a[high])
high--;
if (low >= high) break;
a[low++] = a[high];
while (low < high && a[low] <= part_element)
low++;
if (low >= high) break;
a[high--] = a[low];
}
a[high] = part_element;
return high;
}
void quick_sort(char a[], char low, char high)
{
char middle;
if (low >= high) return;
middle = split(a, low, high);
qscounter++;
quick_sort(a, low, middle - 1);
quick_sort(a, middle + 1, high);
printf("Quick Sort: %d\n", qscounter);
for(int i=0;i<26;i++)
printf("%c",a[i]);
printf("\n\n");
}
void main()
{
char unsorted_alphabet[26] = {'A','E','O','D','B','Q','G','V','Y','J','Z','S','M','N','C','P','F','R','L','T','U','H','W','X','I','K'};
quick_sort(unsorted_alphabet,unsorted_alphabet[0],unsorted_alphabet[25]);
fflush(stdin);
getchar();
}
Решение
Ваш код имеет следующие проблемы:
Вы пытались использовать значение элемента в качестве индекса массива, что, безусловно, было неправильно. Вы передаете [0] и a [25] как индекс в функцию quick_sort, однако, low и high должны быть целочисленного типа, а не char. Вы не можете использовать значение char в качестве индекса, так как значения массива изначально не в порядке, а индексы массива — нет.
Правильный код должен быть следующим:
int split(char a[], int low, int high) //should be integer type for low and high
{
char part_element = a[low];
//if low is a char, what is a[char]? It will not be the value you intended to want
//do same thing in your code
}
void quick_sort(char a[], int low, int high)
{
int middle; //not char
//do same thing as in your code
}
В main () вызов функции должен быть:
quick_sort(unsorted_alphabet,0,25); //should pass array indices
Это на самом деле работает нормально после этих незначительных изменений:
Я получил:
Quick Sort: 20
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Другие решения
Параметры low и high являются индексом массива. Вы можете попробовать позвонить так:
quick_sort(unsorted_alphabet,0,25);