Quick sort i tablica ze stałymi

0

Witajcie moi drodzy! Drugi raz przychodzę do was z problemem dotyczącym sortowania...ten quick sort działa doskonale przy wartościach losowych, ale kiedy próbuję wygenerować tablicę stałą - albo przestaje działać, albo wyświetla jakiś kosmiczny czas :( Probowałem odpalić pod debuggerem, ale program jest przepuszczany i tyle :| Macie jakiś pomysł, co może być przyczyną?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void quick_sort(int tab[],int p, int n) {
  int b=p;
  int pivot = (n+p)/2;
  int pomocnicza_zmienna;
  pomocnicza_zmienna = tab[pivot];
  tab[pivot] = tab[n];
  tab[n] = pomocnicza_zmienna;
  pivot = n;
  int a;
  for (a=p;a<=n-1;a++) {
    if (tab[a] < tab[pivot]) {
      pomocnicza_zmienna = tab[a];
      tab[a] = tab[b];
      tab[b] = pomocnicza_zmienna;
      b++;
    }
  }
  pomocnicza_zmienna = tab[pivot];
  tab[pivot] = tab[b];
  tab[b] = pomocnicza_zmienna;
  pivot = b;
  if (p<pivot) {
    quick_sort(tab,p,pivot);
  }
  if (pivot+1<n) {
    quick_sort(tab,pivot+1,n);
  }
  }

int main() {
  int n;
  double t;
  printf("wpisz liczbę elementów tablicy:");
  scanf("%d",&n);
  int *tab = (int *)malloc(n * sizeof(int));
  int i = 0;
  while (i < n) {
    tab[i] = 1;
    //printf("%d ", tab[i]);
    i = i + 1;
  }
  printf("\n");
  t = clock();
  quick_sort(tab,0,n-1);
  t = clock() - t;
  t = t/CLOCKS_PER_SEC;
  printf("czas to %f\n",t);
  for(int i =0; i<n;i++){
    //printf("%d ", tab[i]);
  }
  free(tab);
  return 0;
}
0

Nad czym tu dumać, masz błąd w programie, pewnie nie jeden. Wygooglaj poprawną implementację ;)

Najprawdopodobniej początkowe a powinno być większe o jeden.

Może coś w tym stylu lepiej zadziała?

int partition(int *arr, int start, int pivot, int end) {
	if (!(start < end)) {
		return start;
	}

	swap(arr[start], arr[pivot]);
	pivot = start;

	int left_end = start + 1;
	for (int right_start = left_end; right_start < end; right_start++) {
		if (arr[right_start] <  arr[pivot]) {
            swap(arr[right_start], arr[left_end]);
			left_end++;
		}
	}

    swap(arr[pivot], arr[left_end-1]);

    return left_end - 1
}


void quick_sort(int *arr, int start, int end) {
	if (!(start < end)) {
		return;
	}

	int pivot = start; // Pivot mozna wybrac w inny sposob.
 	pivot = partition(arr, start, pivot, end);

	quick_sort(arr, start, pivot);
	quick_sort(arr, pivot+1, end);
}

Plus przy partycjonowaniu od lewej do prawej i wyborze stałego piwotu dla tablicy posortowanej (a więc i identycznych wartosci) czas quicksort jest kwadratowy.

0

Kiedy zwiększam "a" o 1, to wtedy dla losowych liczb cały algorytm się sypie... Znalazłem błąd i winne są ostatnie 4 linijki. Kiedy zapisuję je w taki sposób:

int czy_same_stale = 0;
  if (p<pivot-1) {
    for (int check = p;check < pivot - 1;check++) {
        if (tab[check] != tab[pivot-1]) {
        czy_same_stale = 0;
        break;
        }
        else if (check == pivot-2) {
            czy_same_stale = 1;
        }
        }
    if (czy_same_stale == 0) {
    quick_sort(tab,p,pivot-1);
    }
    }
  if (pivot+1<n) {
    for (int check = pivot+1;check < n;check++) {
    if (tab[check] != tab[n]) {
    czy_same_stale = 0;
    break;
    }
    else if (check == n-2) {
        czy_same_stale = 1;
    }
    }
    if (czy_same_stale == 0) {
    quick_sort(tab,pivot+1,n);
  }
  }

to wtedy mój algorytm działa z dobrym czasem i dla losowych wartości i dla stałych. Tylko pytanie: czy to jest jeszcze quick sort? :(

nalik napisał(a):

Nad czym tu dumać, masz błąd w programie, pewnie nie jeden. Wygooglaj poprawną implementację ;)

Najprawdopodobniej początkowe a powinno być większe o jeden.

Może coś w tym stylu lepiej zadziała?

int partition(int *arr, int start, int pivot, int end) {
	if (!(start < end)) {
		return start;
	}

	swap(arr[start], arr[pivot]);
	pivot = start;

	int left_end = start + 1;
	for (int right_start = left_end; right_start < end; right_start++) {
		if (arr[right_start] <  arr[pivot]) {
            swap(arr[right_start], arr[left_end]);
			left_end++;
		}
	}

    swap(arr[pivot], arr[left_end-1]);

    return left_end - 1
}


void quick_sort(int *arr, int start, int end) {
	if (!(start < end)) {
		return;
	}

	int pivot = start; // Pivot mozna wybrac w inny sposob.
 	pivot = partition(arr, start, pivot, end);

	quick_sort(arr, start, pivot);
	quick_sort(arr, pivot+1, end);
}

Plus przy partycjonowaniu od lewej do prawej i wyborze stałego piwotu dla tablicy posortowanej (a więc i identycznych wartosci) czas quicksort jest kwadratowy.

0

Czy z funkcją qsort() z stdlib.h jest coś nie tak?

0

Pytasz, dlaczego jej nie używam i piszę swoją? Taka jest praca domowa

elwis napisał(a):

Czy z funkcją qsort() z stdlib.h jest coś nie tak?

0
nalik napisał(a):

Nad czym tu dumać, masz błąd w programie, pewnie nie jeden. Wygooglaj poprawną implementację ;)

Najprawdopodobniej początkowe a powinno być większe o jeden.

Może coś w tym stylu lepiej zadziała?

int partition(int *arr, int start, int pivot, int end) {
	if (!(start < end)) {
		return start;
	}

	swap(arr[start], arr[pivot]);
	pivot = start;

	int left_end = start + 1;
	for (int right_start = left_end; right_start < end; right_start++) {
		if (arr[right_start] <  arr[pivot]) {
            swap(arr[right_start], arr[left_end]);
			left_end++;
		}
	}

    swap(arr[pivot], arr[left_end-1]);

    return left_end - 1
}


void quick_sort(int *arr, int start, int end) {
	if (!(start < end)) {
		return;
	}

	int pivot = start; // Pivot mozna wybrac w inny sposob.
 	pivot = partition(arr, start, pivot, end);

	quick_sort(arr, start, pivot);
	quick_sort(arr, pivot+1, end);
}

Plus przy partycjonowaniu od lewej do prawej i wyborze stałego piwotu dla tablicy posortowanej (a więc i identycznych wartosci) czas quicksort jest kwadratowy.

Sprawdziłem Twój kod kilka razy i jest podobnie jak z moim, przy kilku tysiącach liczb działa, ale np. dla 50 000 już się nie wykonuje...

0
adam1707 napisał(a):

Sprawdziłem Twój kod kilka razy i jest podobnie jak z moim, przy kilku tysiącach liczb działa, ale np. dla 50 000 już się nie wykonuje...

Tzn? Długo mieli? I dla jakich danych :) Bo jak stałych, to ma złożoność kwadratową jak już Ci to napisałem. U mnie działa.
Pisz dokładniej, bo nie wykonuje się, to nic mi nie mówi.

0
nalik napisał(a):
adam1707 napisał(a):

Sprawdziłem Twój kod kilka razy i jest podobnie jak z moim, przy kilku tysiącach liczb działa, ale np. dla 50 000 już się nie wykonuje...

Tzn? Długo mieli? I dla jakich danych :) Bo jak stałych, to ma złożoność kwadratową jak już Ci to napisałem. U mnie działa.
Pisz dokładniej, bo nie wykonuje się, to nic mi nie mówi.

Wrzucam dokładnie taki kod:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int partition(int *arr, int start, int pivot, int end) {
    int pomocnicza_zmienna;
    if (!(start < end)) {
        return start;
    }
    pomocnicza_zmienna = arr[start];
    arr[start] = arr[pivot];
    arr[pivot] = pomocnicza_zmienna;
    pivot = start;

    int left_end = start + 1;
    for (int right_start = left_end; right_start < end; right_start++) {
        if (arr[right_start] <  arr[pivot]) {
            pomocnicza_zmienna = arr[right_start];
            arr[right_start] = arr[left_end];
            arr[left_end] = pomocnicza_zmienna;
            left_end++;
        }
    }

    pomocnicza_zmienna = arr[pivot];
    arr[pivot] = arr[left_end-1];
    arr[left_end-1] = pomocnicza_zmienna;

    return left_end - 1;
}


void quick_sort(int *arr, int start, int end) {
    if (!(start < end)) {
        return;
    }

    int pivot = start; // Pivot mozna wybrac w inny sposob.
    pivot = partition(arr, start, pivot, end);

    quick_sort(arr, start, pivot);
    quick_sort(arr, pivot+1, end);
}


int main() {
  int n;
  double t;
  printf("wpisz liczbę elementów tablicy:");
  scanf("%d",&n);
  int *tab = (int *)malloc(n * sizeof(int));
  int i = 0;
  //srand(time(0));
  while (i < n) {
    //tab[i] = rand()%(10*n);
    tab[i] = 0;
    //printf("%d ", tab[i]);
    i = i + 1;
  }
  printf("\n");
  t = clock();
  quick_sort(tab,0,n-1);
  t = clock() - t;
  t = t/CLOCKS_PER_SEC;
  printf("czas to %f\n",t);
  for(int i =0; i<n;i++){
    //printf("%d ", tab[i]);
  }
  free(tab);
  return 0;
}

i kiedy za n podaję 50 000, to mam tablicę wypełnioną samymi zerami. To, że długo mieli to jedna sprawa, druga, że nie mieli do końca, bo po kilkunastu sekundach wyświetla się "program przestał działać"

0

Sprawdzasz to na komputerze na parę? ~2.3 sekundy

Przy 500 000 dla Twoich danych rzeczywiście długo trwa. Ale wynika to z tego, że jak już pisałem złożoność jest kwadratowa, a w dodatku wywołuje 500 000 razy funkcję rekurencyjną, co może powodować skończenie się stosu.

Żeby tego uniknąć, można:

  • Zmienić sposób partycjonowania. Tzn. dzielić tablicę na 3 części (Mniejsze od piwotu, równe piwotowi i większe od piwotu).
  • Sprawdzać, czy tablica nie jest już posortowana.
  • Inaczej wybierać piwot. Mediana z 3 wartości. Dla tablicy stałych nie zadziała.
  • Dla małych zakresów wywołać inny algorytm sortowania. Dla stałych nie zadziała.
  • Wywoływać quicksorta tylko do pewnej głębokości. Dokańczać sortowanie innym algorytmem. Ale to już nie jest quicksort, a introsort.
0
nalik napisał(a):

Sprawdzasz to na komputerze na parę? ~2.3 sekundy

Przy 500 000 dla Twoich danych rzeczywiście długo trwa. Ale wynika to z tego, że jak już pisałem złożoność jest kwadratowa, a w dodatku wywołuje 500 000 razy funkcję rekurencyjną, co może powodować skończenie się stosu.

Żeby tego uniknąć, można:

  • Zmienić sposób partycjonowania. Tzn. dzielić tablicę na 3 części (Mniejsze od piwotu, równe piwotowi i większe od piwotu).
  • Sprawdzać, czy tablica nie jest już posortowana.
  • Inaczej wybierać piwot. Mediana z 3 wartości. Dla tablicy stałych nie zadziała.
  • Dla małych zakresów wywołać inny algorytm sortowania. Dla stałych nie zadziała.
  • Wywoływać quicksorta tylko do pewnej głębokości. Dokańczać sortowanie innym algorytmem. Ale to już nie jest quicksort, a introsort.

nie wiem ile razy uruchamiałem ponownie komputer, kopiowałem kod powyżej, nie działało... odinstalowałem code blocksa, zainstalowałem od nowa, zainstalowałem też nowy, inny kompilator, nadal to samo. i nie, nie na komputerze na parę...

1 użytkowników online, w tym zalogowanych: 0, gości: 1