sortowanie quicksort 3 podanych przed uzytkownika cyfr w języku c

Question

Jak ma wyglądać algorytm sortowania quicksort 3 podanych przez uzytkownika  calkowitych liczb w jezyku c?

 

Proszę nie krzyczeć jestem poczatkujący :))

 

 co tu trzeba pozmieniać żeby algorytm działał:

To jest w języku c++ o którym nic nie mam pojęcia:(

int partition(int tablica[], int p, int r) // dzielimy tablice na dwie czesci, w pierwszej wszystkie liczby sa mniejsze badz rowne x, w drugiej wieksze lub rowne od x
{
int x = tablica[p]; // obieramy x
int i = p, j = r, w; // i, j - indeksy w tabeli
while (true) // petla nieskonczona - wychodzimy z niej tylko przez return j nie wiem co tu zmienic
{
while (tablica[j] > x) // dopoki elementy sa wieksze od x
j--;
while (tablica[i] < x) // dopoki elementy sa mniejsze od x
i++;
if (i < j) // zamieniamy miejscami gdy i < j
{
w = tablica[i];
tablica[i] = tablica[j];
tablica[j] = w;
i++;
j--;
}
else // gdy i >= j zwracamy j jako punkt podzialu tablicy
return j;
}
}
 
void quicksort(int tablica[], int p, int r) // sortowanie szybkie
{
int q;
if (p < r)
{  
q = partition(tablica,p,r); // dzielimy tablice na dwie czesci; q oznacza punkt podzialu
quicksort(tablica, p, q); // wywolujemy rekurencyjnie quicksort dla pierwszej czesci tablicy
quicksort(tablica, q+1, r); // wywolujemy rekurencyjnie quicksort dla drugiej czesci tablicy
}
}
 
int main()
{
int ilosc_liczb, i;
cout << "Podaj ilosc licz do posortowania: ";
cin >> ilosc_liczb;
int *tablica = new int [ilosc_liczb]; // utworzenie dynamicznej tablicy na 'ilosc_liczb' elementow
 
for (i = 0; i < ilosc_liczb; i++) // wczytywanie liczb do tablicy
{
cout << "Podaj liczba: ";
cin >> tablica[i];
}
 
quicksort(tablica,0,ilosc_liczb-1); // wywolanie funkcji sortujacej
 
for (i = 0; i < ilosc_liczb; i++) // wypisanie posortowanej tablicy
cout << "tablica[" << i << "] = " << tablica[i] << endl; nie wiem co tu zmienic
 
delete [] tablica; // zwolnienie tablicy zaalokowanej dynamicznie
 
return 0;
}

Comments

Musisz sam pisać sortowanie, czy możesz z standardu skorzystać?

---

#include <stdio.h> 
#include <stdlib.h>
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
} 
  
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];    
    int i = (low - 1);  
  
    for (int j = low; j <= high- 1; j++) 
    { 
        if (arr[j] < pivot) 
        { 
            i++;  
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 
  

void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        int pi = partition(arr, low, high); 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 
  
void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("n"); 
} 
  
int main() 
{ 
    int number = 0;
    scanf("%d", &number);
    int *arr =  malloc (number * sizeof *arr);
    for(int i = 0; i< number; i++)
    {
        int numberUser;
        scanf("%d", &numberUser);
        arr[i]=numberUser;
    }
    quickSort(arr, 0, number-1); 

    printArray(arr, number); 
    free(arr);
    return 0; 
} 

 

---

6
8
7
5
-7
-5
2
-7 -5 2 5 7 8 n

Pierwsza liczba ilość danych, reszta to liczby do posortowania. Twój przykład działa poprawnie. 

https://onlinegdb.com/HJ7tWOSiB

---

Jejku, wiesz, że ten kod jest bardzo prosty w tym aspekcie...

Zmienna "number" odpowiada za ilość wczytywanych danych.

I tak na marginesie, unikaj kolorowania tekstu w swoich postach, komentarzach, bo przy ciemnym motywie nic nie widać.

Answer 1

Quicksort to nazwa algorytmu sortowania danych. Działa poprawnie dla dowolnej ilości danych, nie tylko dla trzech liczb. Trochę kodu trzeba napisać żeby mieć poprawny quicksort, wybacz, ale nie chce mi się klepać oryginalnej wersji, będziesz musiał(a) sam to zrobić. Trochę przykładów jest w necie, np. na wiki:

https://pl.wikipedia.org/wiki/Sortowanie_szybkie

Najważniejsze aspekty to rekurencyjny podział danych na pół. Złożóność odpowiada polu prostokąta  o bokach równych w przybliżeniu N x logN, stąd jego oczekiwana złożoność to NlogN. Są też pułapki i ich rozwiązania - warto poczytać.

Pozdrawiam

Answer 2

Ale partition to mi się kojarzy z mergesort, przykładowy kod napisany na kolanie (mogą być błędy) qsorta wygląda tak (dla typu int):

 

#include <iostream>
#include <cstdlib>
#include <ctime>

void mqsort( int data[] , const int size ) {
    if( size < 2 ) {  // Jeden element albo zero elementów...
        return;       // stanowią zawsze posortowany ciąg.
    }
    {
        const int base = rand() % size;
        const int swp = data[0];
        data[0] = data[base];
        data[base] = swp;
    }
    int split = 1;
    for( int i=1 ; i<size ; i++ ) {
        if( data[0] > data[i] ) {
            const int swp = data[i];
            data[i] = data[split];
            data[split++] = swp;
        }
    }
    mqsort( data , split );
    mqsort( data + split , size - split );
}

int main(int argc, char *argv[]) {
    int data[] = {10,11,-2,7,20,9,9,9,23,18,10};
    srand(time(NULL));
    mqsort( data , (int)(sizeof(data)/sizeof(data[0])) );
    for( int i=0 ; i<(int)(sizeof(data)/sizeof(data[0])) ; i++ ) {
        std::cout << data[i] << std::endl;
    }
    return 0;
}

 

Comments

W C++ to najlepiej na wektorze...

---

Może tak (Ctrl+D) kończy strumień wejściowy. Możesz potem skompilowany program użyć dla plików w powłoce:

shela cat plik | ./qsort

 

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

void mqsort( int data[] , const int size ) {
    // Jeden element albo zero elementów...
    // stanowią zawsze posortowany ciąg.
    if( size < 2 ) {
        return;
    }
    //Losowy element pod index 0, względem indexu 0 będzie podział.
    {
        const int base = rand() % size;
        const int swp = data[0];
        data[0] = data[base];
        data[base] = swp;
    }
    //Przerzuć dane mniejsze od index 0 na początek tablicy.
    int split = 1;
    for( int i=1 ; i<size ; i++ ) {
        if( data[0] > data[i] ) {
            const int swp = data[i];
            data[i] = data[split];
            data[split++] = swp;
        }
    }
    //Posortuj tablice
    mqsort( data , split );
    mqsort( data + split , size - split );
}

int main(int argc, char *argv[]) {
    srand(time(NULL));
    std::vector<int> data;
    while ( ! std::cin.eof() ) {
        int tmp;
        std::cin >> tmp;
        if( ! std::cin.good() ) {
            std::cout << "Niespodziewany format danych" << std::endl;
            break;
        }
        data.push_back( tmp );
    }
    mqsort( data.data() , data.size() );
    for( int i=0 ; i<data.size() ; i++ ) {
        std::cout << data[i] << std::endl;
    }
    return 0;
}

 

---

W C (bez C++) nie ma standardowo (a może są, a ja nie znam) wektorów, nie chce mi się go rzeźbić. W C++ zadziała ten programik dla dowolnej ilości danych, aż zabraknie pamięci i/albo mocy procesora.

To wczytywanie byś musiał zmienić na zapamiętywanie ilości danych i realloc gdy dotychczasowo zaalokowana pamięć nie wystarcza.

---

Nie piszesz w C, używasz rzeczy z C++. C nie ma new i delete. Nie ma też iostream.

---

Tak, C nie ma tego wszystkiego. Te dane byś musiał przemienić na int *dane = (int*)malloc( sizeof(int) * size ). Potem w zmiennej size trzeba pamiętać ile wpisano elementów. Jak ktoś wpisze więcej, to trzeba zrobić dane = (int*)realloc( ... ). std::cin trzeba zamienić na scanf a std::cout na printf - powinno zadziałąć, reszta tak samo.