Форум программистов, компьютерный форум CyberForum.ru

Быстрая сортировка - C++

Восстановить пароль Регистрация
 
Alex_Gnatuyk
2 / 2 / 1
Регистрация: 04.12.2013
Сообщений: 15
25.02.2014, 22:32     Быстрая сортировка #1
Смотрел в тему посвященной быстрой сортировке, и не совсем понял.
написал подобный код. Хотелось бы наиболее подробных комментариев, за что отвечает каждая строчка сортировки, и добавления функции, которая выводит подмассивы после каждой перестановки.


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <ctime>
#include <conio.h>
 
using namespace std;
void input( int *a, int n)
{
    srand(time(NULL));
    for (int i=1; i<=n;i++)
    {
        a[i]= rand(); 
    }
 
}
 
void qsort(int*a, int left, int right)
{
    int w,x,i,j;
    
    
    i=left;  // Левая граница массива
    j=right; 
    
    x=a[(left+right)/2];  //  Выбираем опорным элементом середину массива n/2
    while (i<=j)
    {
        while (a[i]<x) i++;  // Идем по массиву слева пока не найдем элемент, больший опорного x
        while (x<a[j]) j--;  // Когда нашли, идем справа пока не найдем элемент, меньший опорного
        if (i<=j)
        {
            swap(a[i],a[j]);//обмен значениями
            
            
            i++; 
            j--;
        }
    }
    if (left<j) qsort(a,left,j);  // Проверка на продолжение
    if (i<right) qsort(a,i,right);
}
 
 
 
 
 
void output( int *a, int n)
{
    cout << "Элементы отсортированы ";
    cout << "\n" << "\n";
    for (int i=1; i<=n;i++)
    {
        cout << a[i] << "\t" ;
    }
}
 
int main()
{
    int i,n,k,x;
    setlocale(LC_ALL, "RUS");
    cout << "Введите кол-во элемнтов ";
    cin >> n;
 
    cout << "\n" << "\n";
    int *a = new int[n];
    
    input(a,n);
    output(a,n);
    cout << "\n" << "\n";
 
    
 
    
    qsort(a, 0, n);
    
    
    
    output(a,n);
    
    getch();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.02.2014, 22:32     Быстрая сортировка
Посмотрите здесь:

C/C++ FAQ :: Быстрая сортировка (сортировка Хоара) C++
Быстрая сортировка(сортировка Хоара). Отсортировать фрагмент массива C++
C++ Быстрая сортировка
Быстрая сортировка C++
C++ Быстрая сортировка
Быстрая сортировка (сортировка Хоара) для связных списков C++
Быстрая сортировка (сортировка методом Хоара) C++
C++ Сортировка Хоара / Быстрая сортировка

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
25.02.2014, 23:59     Быстрая сортировка #2
Если массив разбить на две части так, чтобы в левой оказались все элементы меньше чем все в правой, то достаточно отсортировать каждую из частей, и весь массив окажется отсортирован!
Yandex
Объявления
25.02.2014, 23:59     Быстрая сортировка
Ответ Создать тему
Опции темы

Текущее время: 18:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru