Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 03.06.2008, 11:41
гость

 
Сообщений: n/a

быстрая сортировка Visual C++
Подскажите, пожалуйста, почему мой код не работает... Вроде, все правильно, а список все равно не сортируется.... При этом вообще все cout после цикла do не работают, то есть вообще ничего на экран не выводится.... Очень надо((((((((((

Код:
#include "stdafx.h"
#include <iostream>
#include <conio.h>

using namespace std;

void swap (int a, int b);
//меняет элементы местами

int _tmain(int argc, _TCHAR* argv[])
{    
    int S[]={22,36,6,79,26,45,75,13,31,62,27,76,33,16,47};
    int i;
    int first=0; //нижняя граница массива
    int mid; //середина mid=(first+last)/2
    int last=14; //верхняя граница массива
    int pivot; //средний элемент массива A[mid]
    int low=1; //первый элемент списка S1
    int high=14; // последний элемент списка S2

    cout << "My Array before sort " << endl;
    for (i=0;i<15;i++)
        cout << S[i] << endl;
        cout << endl;

    mid = (first + last)/2;
    pivot = S[mid];

    swap(S[mid], S[low]);

    low = first + 1;
    high = last;

    do
        {
            while((low <= high) && (S[low] <= pivot))
            low++;
            
            while(S[high] > pivot)
            high--;

            if(low < high)
              {
                  swap(S[low], S[high]);
              }
        } while(low < high);

    S[first] = S[high];
    S[high] = pivot;

    //if(first < high-1)
    // QuickSort(A, low, scanDown-1);
        
    //if(high+1 < last)
    //QuickSort(A, scanDown+1, high);

    cout << "My Array after sort " << endl;
    for (i=0;i<15;i++)
        cout << S[i] << endl;
        cout << endl;
    
    _getch();
    return 0;
}

void swap (int a, int b)
{
    int temp;
    temp=a;
    a=b;
    b=temp;
}

Последний раз редактировалось MBo, 03.06.2008 в 13:52.
  #2  
Старый 03.06.2008, 13:32
гость

 
Сообщений: n/a

У тебя алгоритм реализован неправильно.

QuickSort - рекурсивный алогритм; должна быть как минимум функция с таким именем, дважды рекурсивно вызывающая себя. (в твоем коде эти вызовы закомментированы).

(Его можно сделать нерекурсивным, конечно, через стек, но я бы не рекомендовал тебе, да и вообще никому, пытаться это сделать -- это работа компилятора.)

А еще лучше, почитай какую-нибдуь книжку по алгоритмам (Кормена, например), и пиши quick sort по псевдокоду оттуда.
  #3  
Старый 03.06.2008, 13:36
гость

 
Сообщений: n/a

И еще - твой swap ничего не делает.
Аргументы в C передаются by value, твой swap всего лишь жонглирует своими локальными копиями переменных.
  #4  
Старый 03.06.2008, 13:55
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

пользуйтесь тегом # (CODE), сейчас я подредактировал, чтобы можно было читать

Выделите сортировку в отдельную функцию

в описании аргументов swap * нужно, как гость заметил.


http://algolist.ru/sort/quick_sort.php
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
двоичная (поразрядная) быстрая сортировка незарегистрированный Сортировка и поиск 5 22.05.2010 22:56
Люди помогите, пожалуйста, написать программу на Visual Basice 6.0 Nikolay Оффтопик 14 31.05.2009 07:01
Внешняя сортировка на Visual С++. BitHunter Сортировка и поиск 3 07.05.2008 17:21
Быстрая оболочка Belyaev_Igor Вычислительная геометрия 0 16.03.2008 18:12