Problema com quicksort

[Visitante]

Pessoal, há um tempinho tenho tido problema com o método de organização Quicksort... =/

fiz um programinha aqui que usa o Quick e o BubleSort... o Bubble funciona direitinho... já o Quick não...

e tem mais um bugzinho aqui... mas vamos ao código primeiro... ^^

#include <iostream>
using namespace std;

//------------------------BUBBLESORT---------------------------------
int bubblesort(int vetor[], int n){
  int aux;
  for(int i=0; i<n; i++){
    for(int j=0; j<n-1; j++){
      if(vetor[j+1] < vetor[j]){ 
        aux = vetor[j];
        vetor[j] = vetor[j+1];
        vetor[j+1] = aux;
      }
    }
  }
  cout << "o vetor ordenado e: ";
  for (int k=0; k<n; k++){
    cout << vetor[k] << " ";
  }
}
//---------------MOSTRAR VETOR ORIGINAL-------------------------------
int mostrarvetor (int vetor[], int tamanho){
  cout << "o vetor original e: ";
  int i=0;
  while (i < tamanho){
    cout << vetor[i] << " ";
    i++;
  }
}
//------------------------QUICKSORT-----------------------------------
int quickSort(int arr[], int left, int right) {
  int i=left, j=right;
  int tamanho = right;
  int tmp;
  int pivot = arr[(left + right) / 2];
  while (i <= j){
    while (arr[i] < pivot){
      i++;
    }
    while (arr[j] > pivot){
      j--;
    }
    if (i <= j) {
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
      i++;
      j--;
    }
  }
  if (left < j){
    quickSort(arr, left, j);
  } 
  if (i < right){
    quickSort(arr, i, right);
  }
  for (int k=0; k<tamanho; k++){
    cout << arr[k] << " ";
  }
}
//-----------------------------MAIN----------------------------------

int main (){

    int tamanho, x, i, aux;
    cout << "entre com o tamanho do vetor" << endl;
    cin >> tamanho;
    aux = tamanho/2;
    int vetor[tamanho];
    for (i=0; i<tamanho; i++){
      cout << "digite o valor do elemento numero " << i+1 << " do vetor" << endl;
      cin >> vetor[i];
    }
    cout << "\n";
    i=0;
    inicio:
    cout << "digite o numero da opcao desejada" << endl;
    cout << "******************************" << endl;
    cout << "*1. Verificar vetor original *" << endl;
    cout << "*2. Bubble Sort              *" << endl;
    cout << "*3. Quick Sort               *" << endl;
    cout << "*4. Sair                     *" << endl;
    cout << "******************************" << endl << endl;
    cout << "opcao desejada: ";
    cin >> x;
    cout << "\n";
    switch (x){
      case 1:
        cout << mostrarvetor(vetor, tamanho) << "\n\n";
        goto inicio;
      case 2:
        cout << bubblesort(vetor, tamanho) << "\n\n";
        goto inicio;
      case 3:
        cout << quickSort (vetor, 0, tamanho-1) << "\n\n";
        goto inicio; 
      case 4:
        break;
    system ("pause");
    return 0;
  }
}

o problema é que no menuzinho, quando eu preciono a opção 1 ou 2, depois de mostrar/organizar o vetor, é mostrado também o tamanho do vetor... o_o

já verifiquei o código todo e não sei como/porque é impresso isso ai... '-'

e escolhendo a opção 3 (quicksort), mesmo dando errado, não aparece o tamanho do vetor... u.ú

se puderem me ajudar no quick e nesse probleminha que aparece aí...

é só eu ou vocês também acham o QuickSort tenso de fazer? '-'

valeu!

[ScreenBlack]

A sua lógica está certa.

O que encontrei de errado foi apenas sintaxe, e um erro no "for" que mostra o vetor na função "quickSort", pois tem que ir até "k <= tamanho".

Segue código:

#include <iostream>
using namespace std;

//------------------------BUBBLESORT---------------------------------
void bubblesort(int vetor[], int n){
  int aux;
  for(int i=0; i<n; i++){
    for(int j=0; j<n-1; j++){
      if(vetor[j+1] < vetor[j]){
        aux = vetor[j];
        vetor[j] = vetor[j+1];
        vetor[j+1] = aux;
      }
    }
  }
  cout << "o vetor ordenado e: ";
  for (int k=0; k<n; k++){
    cout << vetor[k] << " ";
  }
}
//---------------MOSTRAR VETOR ORIGINAL-------------------------------
void mostrarvetor (int vetor[], int tamanho){
  cout << "o vetor original e: ";
  int i=0;
  while (i < tamanho){
    cout << vetor[i] << " ";
    i++;
  }
}
//------------------------QUICKSORT-----------------------------------
void quickSort(int arr[], int left, int right) {
  int i=left, j=right;
  int tamanho = right;
  int tmp;
  int pivot = arr[(left + right) / 2];
  while (i <= j){
    while (arr[i] < pivot){
      i++;
    }
    while (arr[j] > pivot){
      j--;
    }
    if (i <= j) {
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
      i++;
      j--;
    }
  }
  if (left < j){
    quickSort(arr, left, j);
  }
  if (i < right){
    quickSort(arr, i, right);
  }
  for (int k=0; k<=tamanho; k++){
    cout << arr[k] << " ";
  }
  cout << endl;
}
//-----------------------------MAIN----------------------------------

int main (){

    int tamanho, x, i, aux;
    cout << "entre com o tamanho do vetor" << endl;
    cin >> tamanho;
    aux = tamanho/2;
    int vetor[tamanho];
    for (i=0; i<tamanho; i++){
      cout << "digite o valor do elemento numero " << i+1 << " do vetor" << endl;
      cin >> vetor[i];
    }
    cout << "\n";
    i=0;
    inicio:
    cout << "digite o numero da opcao desejada" << endl;
    cout << "******************************" << endl;
    cout << "*1. Verificar vetor original *" << endl;
    cout << "*2. Bubble Sort              *" << endl;
    cout << "*3. Quick Sort               *" << endl;
    cout << "*4. Sair                     *" << endl;
    cout << "******************************" << endl << endl;
    cout << "opcao desejada: ";
    cin >> x;
    cout << "\n";
    switch (x){
      case 1:
        mostrarvetor(vetor, tamanho);
        goto inicio;
      case 2:
        bubblesort(vetor, tamanho);
        goto inicio;
      case 3:
        quickSort(vetor, 0, tamanho-1);
        goto inicio;
      case 4:
        break;
  }
    return 0;
}