Próbuję napisać w c++ algorytm sortowania szybkiego. Na razie próbuję jedynie przerzucić dane większe od piwotu "na jego prawą stronę" i mniejsze "na lewą".
#include <iostream>
#include <time.h> // dla time
#include <stdlib.h> // dla rand
#include <math.h>
using namespace std;
int los(int odliczby,int doliczby);
int odległość_na_osi(int liczba1,int liczba2);
void zamiana(int *liczba1,int *liczba2);
int usuń(int liczby[40],int nr_ele,int długość);
void sortowanie_bąbelkowe(int liczby[20],int ileliczb);
void sortowanie_przez_wstawianie(int liczby[40],int długość);
void wstaw(int liczby[40],int nr_ele,int miejsce,int długość);
void sortowanie_przez_wybór(int liczby[40],int długość);
void sortowanie_przez_scalenie(int *ciąg1,int długość1,int *ciąg2,int długość2, int n);
void sortowanie_szybkie(int liczby[40],int długość);
int main()
{
srand(time(NULL));
int liczby[40],*liczby_wsk,*liczby_max;
int ileliczb; //wejście
cin>>ileliczb;
liczby_wsk=&liczby[0];
liczby_max=&liczby[ileliczb-1];
while (liczby_wsk<=(liczby_max)){*liczby_wsk=los(0,20);liczby_wsk++;}
liczby_wsk=&liczby[0]; //wejście
while (liczby_wsk<=(liczby_max)){cout<<*liczby_wsk<<" ";liczby_wsk++;}
liczby_wsk-=ileliczb;cout<<endl;
//int ciąg1[]={7,9,11,13,15};int *ciąg1_wsk=ciąg1;int ciąg2[]={8,10,12,14};int *ciąg2_wsk=ciąg2;
//porównaj(ciąg1,5,ciąg2,4);
/*int a,b;
cin>>a>>b;
cout<<endl;
wstaw(liczby,a,b,ileliczb);
while (liczby_wsk<=(liczby_max)){cout<<*liczby_wsk<<" ";liczby_wsk++;}
liczby_wsk-=ileliczb;cout<<endl;*/
sortowanie_szybkie(liczby,ileliczb);
//sortowanie_przez_scalenie(liczby,ileliczb/2,&liczby[ileliczb/2],ileliczb-(ileliczb/2),ileliczb);
//sortowanie_przez_wybór(liczby,ileliczb);
//sortowanie_przez_wstawianie(liczby,ileliczb);
//sortowanie_bąbelkowe(liczby,ileliczb);
cout<<"\nkoniec";cin>>ileliczb;
}
//**************************************************************************************************************************************
int los(int odliczby,int doliczby)
{
return (odliczby+(rand() % (odległość_na_osi(odliczby,doliczby)+1)));
}
void zamiana(int *liczba1,int *liczba2)
{
int zamiana;
zamiana=*liczba1;
*liczba1=*liczba2;
*liczba2=zamiana;
}
int odległość_na_osi(int liczba1,int liczba2)
{
if (liczba2>liczba1)
{
zamiana(&liczba1,&liczba2);
}
if (liczba1*liczba2>0) return liczba1-liczba2;
else return labs(liczba1)+labs(liczba2);
}
void wstaw(int liczby[40],int nr_ele,int miejsce,int długość) //funkcja wstawia "nr_ele" w określone "miejsce" przesuwając pozostałe liczby
{
int ele=liczby[nr_ele],*liczby_wsk=&liczby[nr_ele];
if (nr_ele<miejsce)
{
for (int i=(nr_ele+1);i<=(miejsce+1);i++,liczby_wsk++)*(liczby_wsk)=*(liczby_wsk+1);
//for (int i=(nr_ele+1);i<=(miejsce+1);i++,liczby_wsk++)*(liczby_wsk-1)=*liczby_wsk;
}
if (nr_ele>miejsce)
{
for (int i=(nr_ele-1);i>=(miejsce-1);i--,liczby_wsk--)*(liczby_wsk)=*(liczby_wsk-1);
//for (int i=(nr_ele-1);i>=(miejsce-1);i--,liczby_wsk--)*(liczby_wsk+1)=*liczby_wsk;
}
liczby[miejsce]=ele;
}
int usuń(int liczby[40],int nr_ele,int długość) //funkcja usuwa element z tablicy
{
int *liczby_wsk=&liczby[nr_ele];
for (int i=(nr_ele+1);i<(długość);i++,liczby_wsk++)*(liczby_wsk)=*(liczby_wsk+1);
return długość-1;
}
//*****************************************************************************************************************************************
void sortowanie_bąbelkowe(int liczby[40],int ileliczb)
{
int *liczby_wsk=&liczby[0];
int koniec=999; //musi tak być bo inaczej program wyświetliłby ostatnie 2 takie same wersy
while (koniec)
{
if(koniec!=999) //musi tak być bo inaczej program wyświetliłby ostatnie 2 takie same wersy
{
for (int i=0;i<ileliczb;++i)cout<<liczby[i]<<" ";
cout<<endl;
}
koniec=0;
for (int i=0;i<(ileliczb-1);++i,liczby_wsk++)
{
if (*liczby_wsk>*(liczby_wsk+1)){zamiana(liczby_wsk,liczby_wsk+1);koniec++;}
}
liczby_wsk-=(ileliczb-1);
//for (int i=0;i<ileliczb-1;++i,liczby_wsk++)cout<<*(liczby_wsk)<<" "; //próbowałem to zrobić wskaźnikami
//liczby_wsk-=(ileliczb-1);
}
cout<<endl;
}
//************************************************************************
void sortowanie_przez_wstawianie(int liczby[40],int długość)
{
int *liczby_max=&liczby[długość-1];
int *liczby_wsk=liczby;
for (int i=0;i<długość;i++)
{
for (int i2=0;i2<i;i2++)
{
if (liczby[i2]>liczby[i])
{
wstaw(liczby,i,i2,długość);
while (liczby_wsk<=(liczby_max)){cout<<*liczby_wsk<<" ";liczby_wsk++;}
liczby_wsk-=długość;cout<<endl;
break;
}
}
}
}
//************************************************************************
void sortowanie_przez_wybór(int liczby[40],int długość)
{
int min=0,*nr_min,koniec;
for (int *wsk_zew=liczby;wsk_zew<&liczby[długość];wsk_zew++)
{
min=*wsk_zew;nr_min=wsk_zew;koniec=0;
for (int *wsk_wew=wsk_zew;wsk_wew<&liczby[długość];wsk_wew++)
{
if (*wsk_wew<min)
{
++koniec;
min=*wsk_wew;
nr_min=wsk_wew;
}
}
if (koniec==0)goto koniec2;
zamiana(wsk_zew,nr_min);
for (int *wsk_wew=liczby;wsk_wew<&liczby[długość];wsk_wew++)cout<<*wsk_wew<<" ";
cout<<endl;
}
koniec2:;
}
//************************************************************************
void sortowanie_przez_scalenie(int *ciąg1,int długość1,int *ciąg2,int długość2,int n)
{
if (długość1>2)sortowanie_przez_scalenie(ciąg1,długość1/2,(ciąg1+długość1/2),długość1-(długość1/2),n); //dzielenie rekurencyjne na mniejsze ciągi
else if (*ciąg1>*(ciąg1+1))zamiana(ciąg1,(ciąg1+1)); //i sortowanie kiedy ciąg ma 2 elementy
if (długość2>2)sortowanie_przez_scalenie(ciąg2,długość2/2,(ciąg2+długość2/2),długość2-(długość2/2),n); //
else if (*ciąg2>*(ciąg2+1))zamiana(ciąg2,(ciąg2+1)); //
int s1=0,s2=0;
int pomocniczy[100];
for (int i=0;i<(długość1+długość2);i++) //sortowanie ciągów
{
if (*(ciąg1+s1)>*(ciąg2+s2))
{
if (s2<(długość2))
{
pomocniczy[i]=*(ciąg2+s2);
s2++;
}
else
{
pomocniczy[i]=*(ciąg1+s1);
s1++;
}
}
else
{
if (s1<(długość1))
{
pomocniczy[i]=*(ciąg1+s1);
s1++;
}
else
{
pomocniczy[i]=*(ciąg2+s2);
s2++;
}
}
}
for (int i=0;i<(długość1+długość2);i++)
{
*(ciąg1+i)=pomocniczy[i];
}
for (int i=0;i<długość1;i++)cout<<*(ciąg1+i)<<" ";cout<<endl; //wypisanie wyników
for (int i=0;i<długość2;i++)cout<<*(ciąg2+i)<<" ";cout<<endl;
if ((długość1+długość2)==n)
{
cout<<"ostatecznie posortowane: "<<endl;
for (int i=0;i<długość1;i++)cout<<*(ciąg1+i)<<" ";
for (int i=0;i<długość2;i++)cout<<*(ciąg2+i)<<" ";
cout<<endl;
}
}
//************************************************************************
void sortowanie_szybkie(int liczby[40],int długość)
{
int *środek=&liczby[długość/2];
int śro=*środek;
*środek=999; //element o wartości 999 dzieli ciąg na liczby mniejsze od śro i liczby większe od śro
int *i=liczby;
while(*i!=999)
{
if (*i>śro){wstaw(liczby,i-liczby,długość,długość);}
else i++;
}
i++;
while(i<&liczby[długość])
{
if (*i<=śro){wstaw(liczby,i-liczby,0,długość);}
else i++;
}
cout<<endl;
for (int i1=0;i1<=długość;i1++)cout<<liczby[i1]<<" "; //wypisanie wyniku
}
Nie wiem czy powinienem wrzucać cały kod. Mój problem dotyczy funkcji sortowanie_szybkie(na samym dole). Wynik(tablica liczby[40]) jest dobry ale
zawsze jeden element należący do tablicy liczby[40] jest śmieciem(-858993460). Nie wiem dlaczego tak się dzieje.
Z góry dzięki za pomoc.
edit.Jeden z elementów tablicy jest smieciem, nie element nr. 40 :D. Zależy to od danych jakie się wylosują.