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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
strange_man
9 / 9 / 0
Регистрация: 17.05.2012
Сообщений: 117
#1

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

05.01.2013, 22:22. Просмотров 630. Ответов 8
Метки нет (Все метки)

нормальный код? а то третий день парюсь, вроде сейчас получилось
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
void quicksort (int *a, int start, int end)
{
    int point = partition (a, start, end); //вызов функции, которая определит окончательную позицию одного элемента и делит массив на подмассивы
 
    //пока в подмасиве не останется один элемент, делаем рекурсивный вызов
    if (point - start >= 1) 
        quicksort (a, start, point-1);
    if (end - point >= 1)
        quicksort (a, point+1, end);
}
 
int partition (int *a, int start, int end)
{
    int pos = start; //определяем позицию элемента, находящегося первым в неотсортированном подмассиве
    while (1)
    {
        int i = end; //счетчик идет с конца подмассива
 
        while ((a[i] >= a[pos]) && (i > pos))
            i--;
 
        //меняем местами элементы в подмассиве, если нужный нам элемент пока не попал в свою позицию
        if (i != pos)
            swap (a[pos], a[i]); //меняем местами элементы массива
        else
        {
            return pos; //возвращаем номер позиции для последующих рекурсивных вызовов
            break;
        }
 
        pos = i;
        i = start + 1;
 
        //по аналогии с предыдущим действием, но теперь в части подмассива слева от элемента
        while ((a[i] <= a[pos]) && (i < pos))
            i++;
 
        if (i != pos)
            swap (a[pos], a[i]);
        else
        {
            return pos;
            break;
        }
 
        pos = i; 
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.01.2013, 22:22     Быстрая сортировка
Посмотрите здесь:

Быстрая сортировка C++
C++ Быстрая сортировка
C++ Быстрая сортировка
C++ Быстрая сортировка
C++ Быстрая сортировка
Быстрая сортировка C++
Быстрая сортировка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Stanis
52 / 41 / 8
Регистрация: 16.12.2012
Сообщений: 144
06.01.2013, 20:29     Быстрая сортировка #2
Ты это по книге Дейтейлов делаешь ?
Igor3D
857 / 443 / 38
Регистрация: 01.10.2012
Сообщений: 2,220
06.01.2013, 20:47     Быстрая сортировка #3
Если исходный массив уже сортирован, то partiton будет все время возвращать start + 1. Не ошибка но работать будет медленно. Можно посмотреть реализацию std::nth_element (но это зрелище не для слабонервных)
strange_man
9 / 9 / 0
Регистрация: 17.05.2012
Сообщений: 117
06.01.2013, 21:10  [ТС]     Быстрая сортировка #4
Stanis, да, по книге Дейтелов.
Stanis
52 / 41 / 8
Регистрация: 16.12.2012
Сообщений: 144
06.01.2013, 21:24     Быстрая сортировка #5
я тоже сегодня пытался написать эту сортировку , весь день . Не понимал как эту функцию partition писать ,
в книге не написано что она должна возвращать номер отсортированного элемента , а сам как то не допер.
В общем пока твой код не увидел не получалось )). Вот сейчас только запустил все работает ) Только
не совсем понимаю момент когда на интервале подмассив начинается не сначала основного массива а
где то в середине и заканчивается не в конце , как программа там что сортирует , ведь мы передаем в
quicksort (начало основного массива ) а не начало подмассива в середине .
AlvinMax
0 / 0 / 0
Регистрация: 05.01.2013
Сообщений: 16
06.01.2013, 22:53     Быстрая сортировка #6
Какая сортировка нужна?
Владслав
-173 / 0 / 1
Регистрация: 02.12.2012
Сообщений: 27
06.01.2013, 23:07     Быстрая сортировка #7
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
#include<iostream>
using namespace std;
#define N 255
int a[N];
void qSort(int l, int r){
int w,x,i,j;
i=l;
j=r;
x=a[(l+r)/2];
while (i<=j){
   while (a[i]<x) i++; // Индекс i последовательно увеличивается до тех пор, пока i-й элемент не превысит опорный.
   while (x<a[j]) j--; // Индекс j последовательно уменьшается до тех пор, пока j-й элемент не окажется меньше опорной.
   if (i<=j){          // Если i <= j — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений i и j, которые были достигнуты.
       w=a[i]; a[i]=a[j]; a[j]=w;
       i++; j--;
   }
}
if (l<j) qSort(l,j); // Рекурсивно упорядочиваем подмассивы,
if (i<r) qSort(i,r); // лежащие слева и справа от опорного элемента.
}
void main()
{
int i,n;
printf("Enter N: "); cin>>n;
for (i=0; i<n; i++){
    cin>>a[i];
}
printf("\n");
qSort(0,n-1);
for (i=0; i<n; i++){
printf("%d ", a[i]);
}
printf("\n");
}
Igor3D
857 / 443 / 38
Регистрация: 01.10.2012
Сообщений: 2,220
07.01.2013, 10:47     Быстрая сортировка #8
Цитата Сообщение от Владслав Посмотреть сообщение
C++
1
2
3
4
x=a[(l+r)/2];
while (i<=j){
   while (a[i]<x) i++; // Индекс i последовательно увеличивается до тех пор, пока i-й элемент не превысит опорный.
}
Если просто "чтобы работало" - то все гуд. А если говорить об оптимальности - то из каких соображений выбран "опорный"? Он может оказаться неудачным, тогда один из новых подмассивов короткий, др длинный.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2013, 23:08     Быстрая сортировка
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Владслав
-173 / 0 / 1
Регистрация: 02.12.2012
Сообщений: 27
25.01.2013, 23:08     Быстрая сортировка #9
Это не гуд
Yandex
Объявления
25.01.2013, 23:08     Быстрая сортировка
Ответ Создать тему
Опции темы

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