[C++][spoj] sort 1

[spammer]

Siemka.

Mam takie jedno zadanko ze spoja o nazwie sort 1 - .

Muszę zaimplementować quicksorta i to jakoś:D posortować.....

Na razie mam coś takiego:

Ukryta treść:    

Kod: Zaznacz cały

#include <iostream>
#include <cstring>

using namespace std;
  
 void qsort(int tab[],int lewy,int prawy)
{
   if(lewy<prawy)
   {
      int m=lewy;
      for(int i=lewy+1;i<=prawy;i++)
         if(tab[i]<tab[lewy])
            swap(tab[++m],tab[i]);
      swap(tab[lewy],tab[m]);
      qsort(tab,lewy,m-1);
      qsort(tab,m+1,prawy);
   }
}
            
  
int main() 
{
      unsigned t;
      string nazwa[1000];
      unsigned n;
      int x[100], y[100];
       
      cin >> t; 
      for(int i = 0; i < t; ++i) 
      {
        cin >> n;
        for(int j = 0; j < n; ++j)
        {
          cin >> nazwa[j];
          cin >> x[j];
          cin >> y[j];
  
        }
  
       
  
       qsort(nazwa[i], 0, n-1);
  
       
  
      for(int j = 0; j < n; ++j)
  
      cout << nazwa[j] << " " << x[j] << " " << y[j] << endl;
  
      cout << endl;
  
      }
  
       
  
return 0;
}

Podczas wywoływania qsort'a jakiś błąd mi wyskakuje. Mógłby ktoś pomóc ??:D

[natkoza]

ja kiedyś napisałam(a moze gdzieś znalazłam.. juz nie pamiętam ) coś takiego

Ukryta treść:    

Kod: Zaznacz cały

#include <iostream>
#include <ctime>
using namespace std;
void quicksort(int tablica[100], int x, int y)
{
int i,j,v,temp;
i=x;
j=y;
v=tablica[div(x+y,2).quot];
do
   {
   while (tablica[i]<v) i++;
   while (v<tablica[j]) j--;
   if (i<=j)
   	{
      temp=tablica[i];
      tablica[i]=tablica[j];
      tablica[j]=temp;
      i++;
      j--;
      }
   }
while (i<=j);
if (x<j) quicksort(tablica,x,j);
if (i<y) quicksort(tablica,i,y);
}
void main(void)
{
int i,ile;
int tablica[10];
cout<<"Ile liczb chcesz posortować (do 100)"<<endl;
cin>>ile;
srand(time(0));
	for(i=0;i<ile;i++)
	{
tablica[i]=rand()%50;
	}
  	
cout<<"Tabica przed posortowaniem"<<endl;
   for(i=0; i<ile; i++)
  	{
   cout<<tablica[i]<<endl;;
   }
quicksort(tablica,0, 9);
cout<<"Tablica po posortowaniu "<<endl;
   for(i=0; i<ile; i++)
  	{
   cout<<tablica[i]<<endl;
   }
}

sortuje on akurat tablice 100 elementową wypełniana losowymi liczbami

[Szemek]

Podczas wywoływania qsort'a jakiś błąd mi wyskakuje. Mógłby ktoś pomóc ??:D

problem nie tkwi w samym qsort, ale w przekazywaniu argumentów do funkcji

Kod: Zaznacz cały

qsort(nazwa[i], 0, n-1);

qsort operuje na int, a ty przekazujesz jedną komórkę tablicy typu string

Kod: Zaznacz cały

int x[100], y[100];

tablice powinny być rozmiaru 1000?


Zastanów się nad tym jak chcesz te dane zgromadzić, w jakiej strukturze (tutaj 3 tablice nie ułatwiają rozwiązania zadania)
A następnie wykorzystaj odpowiednio sortowanie.
I nie zapominaj o głównej treści zadania: Posortuj je względem odległości od środka układu współrzędnych.

[spammer]

Hmmm.
Do zgromadzenia tych danych utworzyłem strukturę.
Zmieniłem algorytm quicksorta na ten, który zakłada, że elementem osiowym jest środkowy element tablicy - nie wiem do końca czy to coś zmienia:p
Jednak nadal kompilator czepia się mnie o ten qsort (błędów jest mniej przy tym powyżej opisanym algorytmie niż przy tym pierwszym).
Chyba chodzi o coś z tą strukturą, bo błąd jest następujący:

Kod: Zaznacz cały

61 C:\sort1.cpp cannot convert `odl' to `void*' for argument `1' to `void qsort(void*, size_t, size_t, int (*)(const void*, const void*))' 

A oto kod:

Ukryta treść:    

Kod: Zaznacz cały

#include <iostream>
#include <cstring>
using namespace std;
 
struct odl
{
  char name[11];
  int x;
  int y;
}; 
  
void quicksort(int tab[], int left, int right){
     int i=left;
     int j=right;
     int x=tab[(left+right)/2];
     do{
         while(tab[i]<x) i++;
         while(tab[j]>x) j--;
         if(i<=j){                  
             int temp=tab[i];
             tab[i++]=tab[j];
             tab[j--]=temp;
         }
     }while(i<=j);
     if(left<j) quicksort(tab,left,j);
     if(right>i) quicksort(tab,i,right);     
}



int odleglosc (int x, int y)
{
  int d;
  d=x*x+y*y;
  return d;
}  
  
            
  
int main() 
{
      unsigned t;
      odl tab[1000];
      int n;
       
      cin >> t; 
      for(int i = 0; i < t; ++i) 
      {
        cin >> n;
        for(int j = 0; j < n; ++j)
        {
          cin >> tab[j].name;
          cin >> tab[j].x;
          cin >> tab[j].y;
        }
  
       
  
       qsort(tab[i], n, odleglosc);
  
       
  
      for(int j = 0; j < n; ++j)
  
      cout << tab[j].name << " " << tab[j].x << " " << tab[j].y << endl;
  
      cout << endl;
  
      }
  
       
  
return 0;
}

[Szemek]

a miałem Ci napisać, żebyś zmienił nazwę funkcji, bo taki algorytm o takiej samej nazwie jest w bibliotece stdlib.h
i właśnie o to pluje się kompilator

widzę już trochę więcej pomyślunku w tym nowym kodzie, ale to jeszcze nie będzie działać
a nie lepiej zrobić strukturę na 4 pola: nazwa, x, y, d?

Kod: Zaznacz cały

qsort(tab[i], n, odleglosc);

źle! złe wywołanie i do tego jeszcze w pętli

sortowanie powinieneś (po wprowadzeniu wszystkich danych!) wywołać np. tak:
sortuj(tablica, indeks_poczatku, indeks_konca)
i w algorytmie przerobić tak, żeby sortować względem ostatniego pola, tj. odległości

[matshadow]

Nie lepiej skorzystać z quicksorta STL-owskiego?

Ukryta treść:    

Kod: Zaznacz cały

#include <iostream>
#include <algorithm>
using namespace std;

struct punkt
{
       string nazwa;
       int x,y;
       double odl;
};

bool funct (punkt a, punkt b)
{
     return a.odl<b.odl;
}

main()
{
      ios_base::sync_with_stdio(0);
      punkt tab[1000];
      int t,n;
      cin>>t;
      while(t--)
      {
         cin>>n;
         for(int i=0;i<n;i++)
         {
           cin>>tab[i].nazwa;
           cin>>tab[i].x>>tab[i].y;
           tab[i].odl=tab[i].x*tab[i].x+tab[i].y*tab[i].y;
         }
         sort(tab,tab+n,funct);
         for(int i=0;i<n;i++)
           cout<<tab[i].nazwa<<" "<<tab[i].x<<" "<<tab[i].y<<endl;
      }
}

[spammer]

No wież Jakby nie to, że to zadanie na kółko, to bym użył właśnie stl'a

PS: Szemek zmieniłem nazwę funkcji i dalej kompilator się mnie czepia

[matshadow]

kółko czy nie kółko, wiem że fajnie jest zabłysnąć samemu napisaną funkcją, ale ja tam wole używać coś, co już jest stworzone

[spammer]

Nie chodzi o to, że zabłysnąć, tylko że nauczyciel kazał napisać samemu quicksort'a

[Szemek]

PS: Szemek zmieniłem nazwę funkcji i dalej kompilator się mnie czepia

Nie tylko o tym pisałem w poprzednim poście.

poniżej działający kod, został zaakceptowany na SPOJu

Ukryta treść:    

Kod: Zaznacz cały

#include<iostream>
#include<string>
using namespace std;

struct punkt
{
       string nazwa;
       int x,y;
       int odl;
};

void zamien(punkt &a, punkt &b)
{
	punkt temp = a;
	a = b;
	b = temp;
}

void sortuj(punkt tab[],int lewy,int prawy)
{
   if(lewy<prawy)
   {
      int m=lewy;
      for(int i=lewy+1;i<=prawy;i++)
		  if(tab[i].odl<tab[lewy].odl)
            zamien(tab[++m],tab[i]);
      zamien(tab[lewy],tab[m]);
      sortuj(tab,lewy,m-1);
      sortuj(tab,m+1,prawy);
   }
}

int main()
{
      ios_base::sync_with_stdio(0);
      punkt tab[1000];
      int t,n;
      cin>>t;
      while(t--)
      {
         cin>>n;
         for(int i=0;i<n;i++)
         {
			 cin>>tab[i].nazwa;
			 cin>>tab[i].x>>tab[i].y;
			 tab[i].odl=tab[i].x*tab[i].x+tab[i].y*tab[i].y;
         }
         sortuj(tab,0,n-1);
         for(int i=0;i<n;i++)
			 cout<<tab[i].nazwa<<" "<<tab[i].x<<" "<<tab[i].y<<endl;
      }
}

Jakby nie to, że to zadanie na kółko, to bym użył właśnie stl'a

Sztuką jest pisanie programów z pewnymi ograniczeniami, ale trzeba też umieć korzystać z gotowych klocków. Zawsze zaczynaj od analizy problemu, a dopiero później zapisu w języku programowania.

[spammer]

Dzięki Szemek za poświęcony czas.
Przeanalizuję ten twój kod i spróbuję na przyszłość go nie popełniać.

Jeszcze raz wielkie dzięki