1

Тема: рекурсивне сортування quicksort

Привіт всім ,стикнувся з пробемою некоректного сортування і відображення .Може хтось допомогти розібратись з проблемою?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>


typedef struct slovechka
{
    char words[25];
    
}SV;

SV* list = (SV*)malloc(1000 * sizeof(SV));
int max;

void number(void);
void slova(void);
void print(void);
void Sort();
void quicksort(char[], int, int, int);




int main()
{
    
    system("chcp 1251");
    system("cls");
    system("color F0");
    number();
    slova();
    print();
    quicksort(list->words, max, 0, max - 1);
    print();
    Sort();
    print();
    
    
    
    

    return 0;
    
    free(list);
    system("pause");
    return 0;
}


void number(void)
{
    printf("Введіть кількість слів: ");
    scanf_s("%ld", &max);
}

void slova(void)
{
    getchar();
    puts("\tВведіть дані");
    for (int i = 0; i < max; i++)
    {
        printf("слово %d: ",i+1);
        scanf("%s", &list[i].words);
        getchar();
    }
    getchar();
}

void print(void)
{
    printf("----------------------------------------------\n");
    slovechka* point;
    int i;
    for (i = 0, point = list; i < max; i++, point++)
    {
        printf("|%-3d|%-20s|\n", i + 1, point->words);    
    }
    printf("----------------------------------------------\n");
}


int cmp(const void* a, const void* b) 
{
    return *(int*)a - *(int*)b;
}

void Sort(void)
{
    qsort(list->words,max,sizeof(slovechka), (int (*)(const void*, const  void*)) strcmp);
}


void quicksort(char h[], int size, int left, int right)
{
    int i = left;
    int j = right;
    char pivot = h[(left + right) / 2];
    char temp;
    while (i <= j)
    {
        while (h[i] < pivot) i++;
        while (h[j] > pivot) j--;
        if (i <= j)
        {
            temp = h[i];
            h[i] = h[j];
            h[j] = temp;
            i++;
            j--;
        }
    }

    if (i < right)
        quicksort(h, size, i, right);
    if (j > left)
        quicksort(h, size, left, j);
}

2

Re: рекурсивне сортування quicksort

Може, ви для початку поясните, в чому саме полягає проблема?

3

Re: рекурсивне сортування quicksort

https://replace.org.ua/uploads/images/9066/927ab1b5f2457fd623c93d92b9b8fd85.png

koala написав:

Може, ви для початку поясните, в чому саме полягає проблема?

Сортування як таке не відбувається+незрозуміло мені з'являються "єє" замість b

Подякували: koala1

4

Re: рекурсивне сортування quicksort

1. _CRT_SECURE_NO_WARNINGS - загалом вимикати попередження - погана практика, краще робити так, як вони радять.
2. Нащо вам C++-ний iostream в коді на чистому C?
3. Ви здійснюєте обмін навіть тоді, коли i==j. Тобто на місці.
4. Змінна size не використовується у функції quicksort; підозрюю, що проблема з "єє" в цьому - i чи j залізають за межі масива і чіпляють зайве значення.
5. Що саме ви сортуєте? quicksort приймає char[] та порівнює за допомогою =, а qsort - SV * та strcmp.

Подякували: svyatvasik, leofun012

5

Re: рекурсивне сортування quicksort

#include <iostream>
#include <stdio.h>

typedef struct wordsort
{
    char words[35];
    
}WD;

void vvid(WD* list, int max);
void vyvid(WD* list, int max);
void Sort(WD* list, int max);
void quicksort(WD* list, int, int);


int main()
{
    system("chcp 1251");
    system("color F0");

    int max;
    WD* list;

    printf("Введіть кількість слів: ");
    scanf_s("%ld", &max);

    list = (WD*)malloc(max * sizeof(WD));


    vvid(list, max);
    vyvid(list, max);
    Sort(list, max);
    vyvid(list, max);
    quicksort(list, 0, max - 1);
    vyvid(list, max);


    free(list);
    //   system( "pause" );
    return 0;
}

void vvid(WD* list, int max)
{
    getchar();
    puts("\nВведіть дані:");
    for (int i = 0; i < max; i++)
    {
        printf("%d. Слово: ", i + 1);
        gets_s(list[i].words);
    
    }
}

void vyvid(WD * list, int max)
{
    printf("\n|Num|Word                |\n");
    int i;
    for (i = 0; i < max; i++, list++)
    {
        printf("|%-3d|%-20s|\n", i + 1, list->words);
    }
    printf("_________________________________________________________________________\n");
}

int comp(const void* a, const void* b)
{
    return strcmp(((const WD*)a)->words, ((const WD*)b)->words);
}
void Sort(WD * list, int max)
{
    qsort(list, max, sizeof(WD), comp);
}


void quicksort(WD* list[], int left, int right)
{
    int i = left;
    int j = right;
    char pivot = list[(left + right) / 2];
    char temp;
    while (i <= j)
    {
        while (list[i] < pivot) i++;
        while (list[j] > pivot) j--;
        if (i <= j)
        {
            temp = list[i];
            list[i] = list[j];
            list[j] = temp;
            i++;
            j--;
        }
    }

    if (i < right)
        quicksort(list, i, right);
    if (j > left)
        quicksort(list,  left, j);
}
koala написав:

1. _CRT_SECURE_NO_WARNINGS - загалом вимикати попередження - погана практика, краще робити так, як вони радять.
2. Нащо вам C++-ний iostream в коді на чистому C?
3. Ви здійснюєте обмін навіть тоді, коли i==j. Тобто на місці.
4. Змінна size не використовується у функції quicksort; підозрюю, що проблема з "єє" в цьому - i чи j залізають за межі масива і чіпляють зайве значення.
5. Що саме ви сортуєте? quicksort приймає char[] та порівнює за допомогою =, а qsort - SV * та strcmp.

1.Спасибі,прийму до уваги
2.iostream для використання system,malloc,strcmp,qsort
3.Не підкажете що додати,я так розумію ще одну умову if(i==j)....

Чисто суть програми зробити ітераційний (нерекурсивний) варіант і рекурсивний варіант реалізації функції сортування

6 Востаннє редагувалося koala (18.04.2019 13:15:23)

Re: рекурсивне сортування quicksort

2. system, malloc, qsort в <cstdlib> <stdlib.h>
strcmp в <cstring> <string.h>, так, випадково підключається з якоюсь іншою бібліотекою, але це не гарантується.
Назви бібліотек <cstring> та <cstdlib> - з C++.
3. Замінити <= на <, вочевидь. І тоді викликати не (від left до j) та (від i до right), а (від left до i) та (від j до right). З урахуванням меж. І ще - треба вирішити, в який половині буде pivot.
Утім, це все не обов'язково робити, просто ефективність коду буде нижчою.
6. Якщо робитимете нерекурсивне швидке сортування, то вам знадобиться стек, щоб зберігати поточні межі сортування.

7

Re: рекурсивне сортування quicksort

svyatvasik написав:

2.iostream для використання system,malloc,strcmp,qsort

Ем.. Це вам студія очі замилює, не ведіться, бо це не правда.