Не получается написать quickSort

@antonk · Регистрация: 17.10.2013

Студворк — интернет-сервис помощи студентам

Добрый вечер. Все тщетно пытаюсь написать быструю сортировку. Читал на википедии и т.д., но все же не могу прояснить несколько моментов.
1) В качестве опорного элемента выбирается медиана последовательности, но как понять когда элементы справа будут меньше опорного элемента, а слева - больше? До каких пор осуществлять частичную сортировку.
2) Как быть, если невозможна ситуация такой частичной сортировки? Например: 1 10 7 2 3 11 4, опорный элемент 2, как нужно сортировать в такой ситуации?
Заранее благодарен за помощь.
Вот пытался написать на Java:

Java
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
import java.util.*;
 
public class quickSort {
    public static void main(String[] args){
        int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        int b = 0;
        int e = a.length - 1;
        func(a, b, e);
    }
    public static void func(int array[], int begin, int end){
        int med = (begin + end - 1) / 2;
        System.out.println();
        int i = 0;
            while(begin != med && end != med){
                while (array[begin] <= array[med]){
                    System.out.println(begin);
                    begin += 1;
                }
                while (array[end] >= array[med]){
                    System.out.println(end);
                    end -= 1;
                }
                if (begin < end){
                    int temp = array[begin];
                    array[begin] = array[end];
                    array[end] = temp;
            }
                System.out.println(i += 1);
    }
 
        func(array, med + 1, end);
        func(array, begin, med - 1);
}
}

@Igor3D · 18.10.2013, 15:26

Сообщение от antonk

2) Как быть, если невозможна ситуация такой частичной сортировки? Например: 1 10 7 2 3 11 4, опорный элемент 2, как нужно сортировать в такой ситуации?

Идем слева направо, 1 < 2, хорошо, продолжаем. 10 > 2, значит 10 надо переставить. Просматриваем справа налево (до 10), нет эл-тов < 2. Значит все, получили 2 подмассива {1} и {10 7 2 3 11 4}, которые парим рекурсивно. Да, не повезло, неудачная медиана, ну бывает и так, будет больше рекурсий

@APALoff · 10.01.2014, 14:21

Сообщение от Igor3D

Просматриваем справа налево (до 10), нет эл-тов < 2.

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .