Быстрая сортировка работает неправильно - C (СИ)
Формулировка задачи:
Здравствуйте!
Разбираюсь с быстрой сортировкой и что-то пошло не так.
Компилятор ни на что не ругается, просто неправильно сортирует и я не могу разобраться почему, поможете?
Здесь структура element, в которой имя, обозначение, ат. масса и т.п. информация об хим. элементе и мне нужно отсортировать все данные по имени в алфавитном порядке, а после их вывести на экран в виде таблицы.
Я для этого создаю массив (чтобы файл оставить без изменений), заполняю его структурами из файла, после сортирую и вывожу.
На
Но выводит тоже самое и почему-то несколько раз...
void quicksort (element a[],int l,int r)
{
element buf, key=a[l];
if (l<r)
{
int i=l+1, j=r;
while (1)
{
while (i<=r && (strcmp(a[i].nameelem,key.nameelem))<0) i++;
while (strcmp(a[j].nameelem,key.nameelem)>0) j--;
if (i>=j) break;
buf=a[i];
a[i]=a[j];
a[j]=buf;
i++; j--;
}
buf=a[j];
a[j]=a[l];
a[l]=buf;
quicksort(a,l,j-1);
quicksort(a,j+1,r);
}
}
void qsort()
{
element el;
system ("cls");
printf("\n Введите имя файла: ");
char filename[80];
fflush(stdin);
gets(filename);
FILE *f;
f=fopen(filename,"rb");
fseek(f,0,2);
int r=ftell(f)/sizeof(element),i;
element mas[r];
rewind(f);
for (i=0;i<r;i++)
fread(&mas[i],sizeof(element),1,f);
fclose(f);
quicksort(mas,0,r-1);
f=fopen(filename,"wb+");
for (i=0;i<r;i++)
fwrite(&mas[i],sizeof(element),1,f);
rewind(f);
printf("\n |--------------------------------------------------------------------------| \n");
printf(" |Ат. н.| Наим. эл.| Хим. обозн.| н. пер.| н. гр.| Ат. масса| Распр. электр.|");
printf("\n |--------------------------------------------------------------------------| ");
while (fread(&el,sizeof(element),1,f))
{
printf("\n |%-6d| %-9s| %-11s| %-7d| %-6d| %-9.3f| %-14d|",el.atnumber,el.nameelem,el.chimicalname,el.numberper,el.numbergroup,el.atmassa,el.electrons);
printf("\n |--------------------------------------------------------------------------| ");
}
system("Pause");
Я понял, что вывожу просто данные из файла, я заменил
while (fread(&el,sizeof(element),1,f))
{
printf("\n |%-6d| %-9s| %-11s| %-7d| %-6d| %-9.3f| %-14d|",el.atnumber,el.nameelem,el.chimicalname,el.numberper,el.numbergroup,el.atmassa,el.electrons);
printf("\n |--------------------------------------------------------------------------| ");
}for (i=0;i<r;i++)
{
printf("\n |%-6d| %-9s| %-11s| %-7d| %-6d| %-9.3f| %-14d|",mas[i].atnumber,mas[i].nameelem,mas[i].chimicalname,mas[i].numberper,mas[i].numbergroup,mas[i].atmassa,mas[i].electrons);
printf("\n |--------------------------------------------------------------------------| ");
}Решение задачи: «Быстрая сортировка работает неправильно»
textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
void quicksort(int a[],int l,int r)
{
int buf, key=a[l];
if (l<r)
{
int i=l+1, j=r;
while (1)
{
while (i<=r && a[i] < key) i++;
while (a[j] > key) j--;
if (i>=j) break;
buf=a[i];
a[i]=a[j];
a[j]=buf;
i++; j--;
}
buf=a[j];
a[j]=a[l];
a[l]=buf;
quicksort(a,l,j-1);
quicksort(a,j+1,r);
}
}
int main(int argc, const char *argv[])
{
int i;
/*int a[] = {8, 6, 2, 3, 4, 9, 10, 1};*/
/*int a[] = {8, 6, 2, 3, 9};*/
int a[] = {4, 9, 7, 6, 2, 3};
int size = sizeof(a)/sizeof(int);
for (i = 0; i < size; i++) {
printf("%d ", a[i]);
}
printf("\n");
quicksort(a, 0, size - 1);
for (i = 0; i < size; i++) {
printf("%d ", a[i]);
}
printf("\n");
exit(EXIT_SUCCESS);
}
Объяснение кода листинга программы
- Включаются необходимые заголовочные файлы: stdio.h и stdlib.h
- Определяется функция quicksort, которая реализует быструю сортировку
- В функции main создается массив a размером 5, заполненный случайными значениями от 1 до 9
- Выводится на экран содержимое массива a
- Вызывается функция quicksort для сортировки массива a в порядке возрастания
- Выводится на экран отсортированный массив a
- Программа успешно завершается