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.

czyli jak wnioskuje z postow da to sie zrobic w jednej petli...

a = -1;
hahaha - ale chamski myk [green] - no ale fakt - jest jedna pętla :) [soczek]

Jakoś nie widzę tego rekurencyjnego sortowania, tzn. nie żebym nie wierzył, że istnieje ;> Ale chodzi mi o przybliżenie idei jego działania. Wiem, że można rekurencyjnie posortować połówki tablicy i je scalić, no ale tu już jest pętla - przynajmniej narzuca się w naturalny sposób przy scalaniu ciągów. Chyba, że jakieś rekurencyjne scalanie, albo zupełnie inna rekurencja do posortowania. Anyway jak ktoś ma chwilę i chce przybliżyć tę rekurencję dla potomnych to z chęcią poczytam.

pzdr,
y.

mysle, ze rekurencyjnie to mozna by np. tak:

#include <iostream>

using namespace std;

void sortuj_rek(int *dane, int ile)
{
  int p;
  switch (ile)
  {
    case 0:
    case 1:
     break;
    case 2:
     if (dane[0] > dane[1])
     {
       p = dane[0];
       dane[0] = dane[1];
       dane[1] = p;
     }
     break;
    default:
     sortuj_rek(dane, 2);
     sortuj_rek(dane + 1, ile - 1);
     sortuj_rek(dane, ile - 1);
  }
}

int main()
{
  const int ROZMIAR = 10;
  int dane[ROZMIAR];

  cout << "Przed\n\n";
  for (int i = 0; i < ROZMIAR; i++)
   cout << dane[i] << endl;

  sortuj_rek(dane, ROZMIAR);

  cout <<"\nPo\n\n";
  for (int i = 0; i < ROZMIAR; i++)
   cout << dane[i] << endl;

  cin.get();
  return 0;
}

mozna tez tak ,

inline void przestaw(int & a,int &b) 

int temp=a;
a=b;
b=temp;


}

void  szybkie(int tablica[size],int lewy,int prawy)
{
if (lewy < prawy)
{
int m=lewy;
for(int i=lewy+1;i<=prawy;i++)
{


if (tablica[i]<tablica[lewy])
{

przestaw(tablica[++m],tablica[i]);

}
}
przestaw(tablica[lewy],tablica[m]);
szybkie(tablica,lewy,m-1);
szybkie(tablica,m+1,prawy);

}

}