[c]Problemy z programem sortowań WAŻNE!

[ogrod87 0]

Witam, oto mój program:

#include <stdio.h>	 //biblioteki potrzebne do obsługi programu
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#define N 10 //deklaracja stałej globalnej N=10

void wpisz_do_tablicy(int *); //deklaracja funkcji z prototypem wywolujaca wpisanie danych do tablicy
void wyswietl_tablice(int *); //deklaracja funkcji z prorotypem wywołująca wyświetlenie danych wpisanych do tablicy
void sortowanie_babelkowe(int *); //deklaracja funkcji z prototypem wywołująca sortowanie bąbelkowe
void sortowanie_szybkie(int *,int,int); //deklaracja funkcji z prototypem wywołująca sortowanie szybkie(quick sort)
void sortowanie_przez_proste_wstawianie(int *); //deklaracja funkcji z prototypem wywołująca sortowanie przez proste wstawianie
void sortowanie_przez_proste_wybieranie(int *); //deklaracja funkcji z prototypem wywołująca sortowanie przez proste wybieranie
void sortowanie_stogowe(int *); //deklaracja funkcji z prototypem wywołująca sortowanie stogowe
void budowanie_rozbieranie_kopca(int *,int,int);  //deklaracja funkkcji z prototypem, która buduje oraz rozbiera kopiec
void sortowanie_przez_scalanie(int *,int*); //deklaracja funkcji z prototypem wywołująca sortowanie przez scalanie
void sort_scalanie(int *,int*,int,int); //deklaracja funkcji z prototypem wywołująca sortowanie przez scalanie
void scalanie(int *,int*,int,int,int); //deklaracja funkcji z prototypem wywołująca scalanie

//*************************************************************************
int main()
{  int tablica[N],bufor_scalanie[N],x,poczatek,koniec,wynik,i; //deklaracja zmiennych
  while(!kbhit());
  printf("\nProsze uzupelnic tablice: \n");
  wpisz_do_tablicy(tablica); //wywołanie funkcji wpisania danych do tablicy
  printf("\nPodane liczby to:\n");
  wyswietl_tablice(tablica); //wywołanie funkcji wyswietlenia danych wpisanych do tablicy
  printf("\n");
  printf("\nRodzaje sortowan: ");
  printf("\n1.Sortowanie Babelkowe");
  printf("\n2.Sortowanie Szybkie");
  printf("\n3.Sortowanie Przez Proste Wstawianie");
  printf("\n4.Sortowanie Przez Proste Wybieranie");
  printf("\n5.Sortowanie Stogowe");
  printf("\n6.Sortowanie Przez Scalanie");
wybor: printf("\nProsze wybrac cyfre odpowiadajaca sortowaniu: "); //etykieta wybor:
   scanf("%d",&x);
  if (x<=0 || x>=7)	//jeśli x jest mniejsze,równe 0 lub większe, równe 7...
  {   
   printf("\nWybrano zla cyfre"); 
   goto wybor; //...wróć do etykiety wybór
  }
  switch(x) // w zależności od x wybierz:...
  { 
	case 1: sortowanie_babelkowe(tablica); break; //...jeśli x=1 wywołaj funkcję sortowania bąbelkowego
	case 2: sortowanie_szybkie(tablica,0,N); break; //...jeśli x=2 wywołaj funkcję sortowania szybkiego
	case 3: sortowanie_przez_proste_wstawianie(tablica); break; //...jeśli x=3 wywołaj funkcję sortowania przez proste wstawianie
	case 4: sortowanie_przez_proste_wybieranie(tablica); break; //...jeśli x=4 wywołaj funkcję sortowania przez proste wybieranie
	case 5: sortowanie_stogowe(tablica); break; //...jeśli x=5 wywołaj funkcję sortowania stogowego
	case 6: sortowanie_przez_scalanie(tablica,bufor_scalanie); break; //...jeśli x=6 wywołaj funkcję sortowania przez scalanie
  }
  printf("\nCiag posortowany: ");
  wyswietl_tablice(tablica); //wywołanie funkcji wyswietlenia,w tym miejscu posortowanych danych, wpisanych do tablicy
  printf("\n\nKoniec programu, prosze nacisnac dowolny klawisz....");
  while(!kbhit());	
  return 0;
}
//*************************************************************************
void wpisz_do_tablicy(int tablica[N])
{  int i;
  for(i=0;i<N;i++)
{ 
   printf("Prosze podac %d liczbe: ",(i+1)); 
   scanf("%d",&tablica[i]); 
}
}
//*************************************************************************
void wyswietl_tablice(int tablica[N])
{  int i;
  for(i=0;i<N;i++)
  {
   printf("%d",tablica[i]); 
   if(i<(N-1)) 
   printf(","); 
  }
}
//*************************************************************************
void sortowanie_babelkowe(int tablica[N])
{
  int i,j,bufor,a=1;
  for(i=0;i<N;i++)
{	for(j=N-1;j>=i;j--)
		 if(tablica[j-1]>tablica[j]) //jeśli tablica[j-1] jest większa od tablica[j] 
		 {	
			  bufor=tablica[j-1];  //wpisz wartość tablica[j-1] do bufora
			  tablica[j-1]=tablica[j]; //wpisz wartość tablica[j] do tablica[j-1]
			  tablica[j]=bufor; //wpisz wartość tablica[j] do bufora

		 }
}
}
//*************************************************************************
void sortowanie_szybkie(int tablica[N],int poczatek, int koniec)
{  int i,j,bufor;
  int x;
  x=tablica[(poczatek+koniec)/2]; //podziel ciag na 2 czesci
  i=poczatek;
  j=koniec;
  do
  {
  while(tablica[i]<x) ++i;
  while(tablica[j]>x) --j;
  if(i<=j)
  {
	 bufor=tablica[i]; //wpisz wartość bufora do tablica[i] 
	 tablica[i]=tablica[j]; //wpisz wartość tablica[i] do tablica[j]
	 tablica[j]=bufor; //wpisz wartość tablica[j] do bufora
	 ++i; //inkrementuj i
	 --j; //inkrementuj j
  }
  } 
  while(i<j);
  if(poczatek<j) //jeśli poczatek jest większy większy od j(koniec)
  sortowanie_szybkie(tablica,poczatek,j); //wywołaj funkcję sortowania szybkiego
  if(koniec>i) //jeśli koniec jest większy od i(początek)
  sortowanie_szybkie(tablica,i,koniec); //wywołaj funkcję sortowania szybkiego
}
//*************************************************************************
void sortowanie_przez_proste_wstawianie(int tablica[N])
{  int i,j,bufor;
  for(i=1;i<N;i++)
  {	
   bufor=tablica[i]; //wpisz wartość bufora do tablica[i] 
  for(j=i-1;(j>=0) && (bufor<tablica[j]);j--) 
  {
	 tablica[j+1]=tablica[j]; //wpisz wartość tablica[j+1] do tablica[j]
	 tablica[j]=bufor; //wpisz wartość tablica[j] do bufora
  }
  }
} 
//*************************************************************************
void sortowanie_przez_proste_wybieranie(int tablica[N])
{ int i,j,k,bufor;
 for(i=0;i<N-1;i++)
  {
  k=i;
  for(j=i+1; j<N; j++)
	 if(tablica[k]>tablica[j]) //jeżeli tablica[j] jest większa od tablica[i]
		k=j; //wpisz wartość k do j
		bufor=tablica[i]; //wpisz wartość bufora do tablica[i] 
		tablica[i]=tablica[k]; //wpisz wartość tablica[i] do tablica[k] 
		tablica[k]=bufor; //wpisz wartość tablica[k] do bufora
  }
}
//*************************************************************************
void sortowanie_stogowe(int tablica[N])
{ int i,bufor;
 for(i=(N/2)-1;i>=0;i--)
 budowanie_rozbieranie_kopca(tablica,i,N); //wywołaj funkcę budowania i rozbudowania kopca
 for(i=(N-1);i>=1;i--)
 {
 bufor=tablica[0]; //wpisz wartość tablica[0] do bufora
 tablica[0]=tablica[i]; //wpisz wartość tablica[1] do tablica[0]
 tablica[i]=bufor; //wpisz wartość tablica[i] do bufora
 budowanie_rozbieranie_kopca(tablica,0,i-1);  //wywołaj funkcę budowania i rozbudowania kopca
 }
}
void budowanie_rozbieranie_kopca(int tablica[N],int korzen,int ostatni)  
{  int gotowe,max_potomek,bufor;
  gotowe=0;
  while(((korzen*2)<=ostatni)&&(!gotowe))
  {
  if((korzen*2)==ostatni) //jeżeli wartość (korzeń*2) równa się wartości ostatni
	 max_potomek=(korzen*2); //przypisz wartość (korzeń*2) do maksymalnego potomka
	 else if(tablica[(korzen*2)]>tablica[(korzen*2)+1]) //lub jeżeli tablica[korzeń*2] jest większa od tablica[(korzeń*2)+1]
		max_potomek=(korzen*2); //przypisz wartość (korzeń*2) do maksymalnego potomka
	 else //w innym przypadku
		max_potomek=(korzen*2)+1; //przypisz wartość (korzeń*2)+1 do maksymalnego potomka
  if(tablica[korzen]<tablica[max_potomek]) //jeżeli tablica[korzeń] jest mniejsza od tablica[max_potomek]
  {
	 bufor=tablica[korzen]; //wpisz wartość tablica[korzen] do bufora
	 tablica[korzen]=tablica[max_potomek]; //wpisz wartość tablica[max_potomek] do tablica[korzeń]
	 tablica[max_potomek]=bufor; //wpisz wartość bufora do tablica[max_potomek]
	 korzen=max_potomek; //wpisz wartośc maksymalnego potomka do korzenia
  }
  else //w innym przypadku
	 gotowe=1; //zasygnalizuj, że kopiec został zrobiony
 } 
} 
//*************************************************************************
void sortowanie_przez_scalanie(int tablica[N],int bufor[N])
{
 sort_scalanie(tablica,bufor,0,(N-1));
}
void sort_scalanie(int tablica[N],int bufor[N],int lewy,int prawy) //wywołaj funkcję sortowania
{ int srednia;
 if(prawy>lewy) //jeśli prawa strona jest większa od lewej strony
 {
srednia=(prawy+lewy)/2; //oblicz srednia
sort_scalanie(tablica,bufor,lewy,srednia); //wywołaj funkcję sortowania
sort_scalanie(tablica,bufor,(srednia+1),prawy); //wywołaj funkcję sortowania
scalanie(tablica,bufor,lewy,(srednia+1),prawy); //wywołaj funkcję sortowania
 }	 
}
void scalanie(int tablica[N],int bufor[N],int lewy,int srednia,int prawy)
{ int i,lewy_koniec,liczba_elementow,bufor_pozycji;
 lewy_koniec=(srednia-1); //przypisz wartość średniej-1 do lewego końca
 bufor_pozycji=lewy; //przypisz wartość lewej strony do bufora pozycji
 liczba_elementow=prawy-lewy+1;// przypisz wartość prawej strony-lewa strona+1 do liczby elementów
 while((lewy<=lewy_koniec) && (srednia<=prawy))
 {
if(tablica[lewy]<=tablica[srednia]) //jeżeli tablica[srednia] jest mniejszy lub równy tablica[srednia]
{
  bufor[bufor_pozycji]=tablica[lewy];//przypisz tablica[srednia] do bufor[bufor_pozycji]
  bufor_pozycji=bufor_pozycji+1; //przypisz wartość  bufor_pozycji+1 do bufor_pozycji
  lewy=lewy+1; //przypisz wartość lewej strony+1 do lewej strony
}
else //w innym przypadku
{
  bufor[bufor_pozycji]=tablica[srednia]; //przypisz wartość  tablica[srednia] do bufor[bufor_pozycji]
  bufor_pozycji=bufor_pozycji+1; //przypisz wartość  bufor_pozycji+1 do bufor_pozycji
  srednia=srednia+1; //przypisz wartość średniej+1 do średniej
}
 }
 while(lewy<=lewy_koniec)
 {
bufor[bufor_pozycji]=tablica[lewy]; //przypisz wartość  tablica[lewy] do bufor[bufor_pozycji]
lewy=lewy+1; //przypisz wartość lewej strony+1 do lewej strony
bufor_pozycji=bufor_pozycji+1; //przypisz wartość  bufor_pozycji+1 do bufor_pozycji
 }
 while(srednia<=prawy)
 {
bufor[bufor_pozycji]=tablica[srednia]; //przypisz wartość  tablica[srednia] do bufor[bufor_pozycji]
srednia=srednia+1; //przypisz wartość średniej+1 do średniej
bufor_pozycji=bufor_pozycji+1;  //przypisz wartość  bufor_pozycji+1 do bufor_pozycji
 }
 for (i=0;i<=liczba_elementow;i++)
 {
tablica[prawy]=bufor[prawy]; //przypisz wartość bufor[prawy] do tablica[prawy]
prawy=prawy-1; //przypisz wartość prawej strony+1 do prawej strony
 }
}

 

Program ma za zadanie pokazania działania sortowań.

Wysłałem go wykładowcy, lecz dostałem takie o zastrzeżenia:

 

1. Poprawi Pan bąbelkowe i uodporni Pan program na wprowadzanie liter i

innych znaków.

2. będzie można wprowadzać liczby po przecinku (spacji), a nie każdą po

wyświetleniu pytania. Czyli tak: "Proszę podać liczby do posortowania:"

i użytkownik podaje: 9,8,7,6,5,4,3,2,1 (naciska enter).

3. program po posortowaniu musi wrócić do menu z opcjami "wprowadź inne

liczby" i "posortuj innym algorytmem", a nie kończyć aplikację.

4.Program będzie wyświetlał krok po kroku działanie sortowań...

 

Problem w tym, że muszę wysłać ten program do jutra do północy, a nie mam za bardzo pomysłu, jak poprawić te 4 punkty, a tylko w przypadku ich poprawenia program zostanie zaliczony.

Czy ktoś mógłby mi pomóc?

Z góry dzięki

 

Ps. Nie patrzcie na komentarze ;P one muszę być, bo bez komentarzy wykładowca nawet nie patrzy na kod

[Bono[UG] 1920]

1. bąbelkowe

Masz złą 2 pętle.

Za każdym przejściem 1 pętli element maksymalny jest przesuwany na koniec tablicy. Druga pętla powinna więc pomijać ostatnie elementy.

U Ciebie pomija pierwsze.

Musisz zmienić warunek - dać od 0 do N-i

 

Z poprawnymi danymi, to nie do końca pamiętam jak się zachowuje scanf przy błędnych danych. Może wystarczy sprawdzić czy nie zwróci kodu błędu i wtedy poprosić o powtórne wpisanie.

Albo czytać znaki z klawiatury (getch lub getchar - nie pamiętam), sprawdzać czy to cyfry i tworzyć z nich liczby. Jak trafi na przecinek lub spację to przechodzi do następnej liczby.

 

2. Jeżeli po spacji, to wywal printf'a i daj go przed for'a ("podaj N liczb). Czy przecinki też pominie, to nie wiem wypróbuj. Możesz dodać w pętli, żeby pisało ile już liczb zostało wprowadzonych.

 

3. Możesz dać całe menu (razem ze switch) w pętlę, która się skończy po wybraniu odpowiedniej opcji.

Możesz dodać do wyboru zmień liczby lub po zakończeniu sortowania dodać mini menu (nowa funkcja) z możliwością wprowadzenia nowych liczb, sortowania innym algorytmem (koniec funkcji i powrót do głównego menu), koniec programu.

 

4. Dajesz printf'a po każdej zmianie tablicy, żeby było widać co się dzieje.

 

Wracam jutro, więc pewnie coś posuniesz do przodu.

Jak będzie kłopot z menu, to postaram się poszukać starych programów gdzie miałem.

[ogrod87 0]

dzięki, pogrzebię i w razie czego dam cynk