sortowanie w 1 petli

da sie zrobic jakies proste sortowanie tablicy liczb w jednej petli ??

wtedy qsort nie będize takie szybkie

Głowy nie dam, ale chyba nie istnieje algorytm sortujący w jednej pętli. Potrzebne są przynajmniej dwie. Jedna przejrzy dane i zapamięta pewne informacje a druga na podstawie tych informacji przetasuje elementy w odpowiedniej kolejności.

Kiedyś się nad tym zastanawiałem i nie wymyślilem sortowania na 1 petli - jeśli się mylę, to zarzućcie przykładem - jestem ciekaw :)

Jesli mamy np. do posortowanie niepowtarzajace sie liczby naturalne np. nie przekraczajace 10000 to mozemy sobie zrobic tablice 10000 bitow i w jednej petli ustawiac bity o numerach takich jak kolejne dane wejsciowe i juz mamy posortowane ;)

a cos takiego:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#define TAB_SIZE 10
int main()
{
 int a, t, tab[TAB_SIZE];
 time_t czas;

 time(&czas);
 srand(czas);

 printf("\n\n");

 for(a = 0; a < TAB_SIZE; a++)
  tab[a] = rand()%100;

 for(a = 0; a < TAB_SIZE; a++)
  printf("%d ", tab[a]);

 for(a = 0; a < TAB_SIZE - 1; a++){
  if(tab[a] > tab[a+1]){
    t = tab[a];
    tab[a] = tab[a+1];
    tab[a+1] = t;
    a = -1;
  }
 }

printf("\n");

for(a = 0; a < TAB_SIZE; a++)
  printf("%d ", tab[a]);

getch();
return 0;
}

jesli sa jakies bledy lub przypadek kiedy algorytm zle zadziala to prosze o odpowiedz

Przecież miało być w jednej pętli. A są 4. :>

Mam lepszą zagadkę - czy da się posortować nie używając pętli w ogóle? [green]
Oczywiście nie chodzi mi o przypadek trywialny, kiedy mamy 3 liczby.

Ja bym obstawiał, że się nie da. Już na wczytanie ustalonej ilości obiektów trzeba pętli ;> Gdyby się dało bez pętli to oznaczałoby, że da się posortować w stałej liczbie kroków bez względu na wielkość danych, a to chyba tylko jakaś wymyślona maszyna mogła by zrobić ;) Jeśli się da to z chęcią bym zobaczył takie rozwiązanie i przyjęte ograniczenia na obiekty do posortowania.

pzdr,
y.

czy da się posortować nie używając pętli w ogóle?

Nie widze problemu... zamiast petli można uzyc rekurencji

(Billi cofam, posortuje... nie zauważyłem a=-1 ;) )

Nie widze problemu... zamiast petli można uzyc rekurencji

No i zepsules cala zabawe... Myslalem, ze bedzie wiecej postow udowadaniajacych, ze sie nie da. :d

Krolik: sortujaca petla jest tylko jedna, reszta to wypelnienie tablicy i jej wypisanie.