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

@_Studentka_ · Регистрация: 20.11.2009

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

Помогите,пожалуйста,исправить ошибки. Уже вторые сутки сижу над кодом и не могу понять в чем я ошибаюсь. Логика вроде правильная, но вот не сортирует.((
package quicksort;

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
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Vector;
 
/**
 *
 * @author Администратор
 */
public class Quick1 {
    Vector<Integer>ob;
    int t,tem,temp,size;
    Quick1(){
        ob = new Vector<Integer>();
     
        t=0;
        temp=0;
        size=0;
     
        
 
    }
void menu() throws IOException{
    Scanner in = new Scanner(System.in);
    while(t!=3){
 
 
    System.out.println();
    System.out.println("____________________");
    System.out.println("________MENU________");
    System.out.println("____________________ ");
    System.out.println("Please,select operation");
    System.out.println("1)Add element to list");
    System.out.println("2) Sorting");
    System.out.println("3)Exit");
    System.out.println("------------------------>");
    t=in.nextInt();
    switch(t){
        case 1: AddElement();break;
        case 2: quickSort();break;
        case 3:{
            System.out.println("The end");
            System.out.println("Thank you for using this program");
            System.out.println("--------------------------------->");
            System.exit(0);break;
        }
        default:
            System.out.println("Enter correct value");
    }
    }
}
void AddElement() throws IOException{
    System.out.println("Enter your value->");
    BufferedReader is = new BufferedReader(new InputStreamReader(System.in));
    int is1 = Integer.valueOf(is.readLine());
    ob.add(is1);
    size++;
    
 System.out.println("your value was added");
    System.out.println("Unsorted list");
    for(int i=0;i<size;i++){
        System.out.print(ob.get(i)+ "\t");
 
    }
}
 void quickSort() {
        int startIndex = 0;
        int endIndex = size;
        doSort(startIndex, endIndex);
    }
 
    void doSort(int start, int end) {
        if (start >= end)
            return;
        int i = start, j = end;
        int cur = i-(i-j)/ 2;
        while (i < j) {
            int a = ob.get(i);
            int b = ob.get(cur);
            int c = ob.get(j);
            while (i < cur && a <= b) {
                i++;
            }
            while (j > cur && b <= c) {
                j--;
            }
            if (i < j) {
                 temp = ob.get(i);
                 
                 ob.set(i,c);
                 ob.set(j, temp);
 
                if (i == cur)
                    cur = j;
                else if (j == cur)
                    cur = i;
            }
        }
 
        doSort(start, cur);
        doSort(cur+1, end);
 
    }
}

@lifestyle · 21.11.2009, 11:36

Ну вопервых ИМХО не стоило строить обьект QUICK1.Вектор у вас есть готовый джавовский и зачем придумывать велосипед самостоятельно написав функции АДД... вообщем:
1)код БЫСТРОЙ СОРТИРОВКИ не правильный был
2) Так как вы построили обьект QUICK1 то к нему необходимо и конструктор написать.у вас он тоже отсутствовал.
а вообще все это можно было напистаь намного проще в несколько функций))))вот исправленный код,если есть желаение-потребность могу выслать код без Обьекта а просто через несколько функций хотя вы и сами сможете легко его написать...(читайте коментарий к коду)

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
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Vector;
import java.util.*;
 
/**
 *
 * @author Администратор
 */
public class Quick1 {
    Vector<Integer> ob;
    int t,tem,temp,size;
    public  Quick1(){  //CONSTRUCTOR
        this.ob = new Vector<Integer>();
        this.t=0;
        this.temp=0;
        this.size=0;
    }
    public Quick1(Quick1 other){ //COPY CONSTRUCTOR  впринципе его можно было тут и не пистать он не используеться в этой программе
        this.ob =other.ob;
        this.t= other.t;
        this.temp=other.temp;
        this.size=other.size;
    }
    void menu() throws IOException{
        Scanner in = new Scanner(System.in);
        while(t!=3){
            System.out.println();
            System.out.println("____________________");
            System.out.println("________MENU________");
            System.out.println("____________________ ");
            System.out.println("Please,select operation");
            System.out.println("1)Add element to list");
            System.out.println("2) Sorting");
            System.out.println("3)Exit");
            System.out.println("SIZE:"+this.ob.size());
            System.out.println("------------------------>");
            t=in.nextInt();
            switch(t){
            case 1: AddElement();break;
            case 2: {
                    quickSort1(this.ob); // отсылает насортировку вектор.
                    System.out.print("Sorted List is: ");
                    for(int i=0;i<this.ob.size();i++){
                        System.out.print(this.ob.get(i)+" ");
                    }
                    System.out.println();
                    break;
            }
            case 3:{
                System.out.println("The end");
                System.out.println("Thank you for using this program");
                
                System.out.println("--------------------------------->");
                System.exit(0);break;
            }
            default:
                System.out.println("Enter correct value");
            }
        }
    }
        private static  int partition(Vector<Integer> MyVector, int low, int high){
            int pivot;
            pivot = low;
            low = low + 1;
            int x = MyVector.get(pivot);
            while (low <= high){
                if (MyVector.get(low) <= x){
                    low = low + 1;
                    
                }
                else if (MyVector.get(high) > x){               
                    high = high - 1;
                }
                else{
                    swap(MyVector, low, high);
                }
            }
            swap(MyVector, high, pivot);   
            pivot = high;
            return pivot; 
        }
 
        public static  void quick_sort(Vector<Integer> MyVector, int low, int high){
            int pivot;
            if (low < high){
                pivot = partition(MyVector, low, high);
                quick_sort(MyVector, low, pivot-1);
                quick_sort(MyVector, pivot+1, high);
            }
        }
 
        public static void quickSort1(Vector<Integer> MyVector){
            int size=MyVector.size();
            quick_sort(MyVector, 0, size-1 );
        }
        public static void swap(Vector<Integer> MyVector, int i, int j){
            int temp =MyVector.get(i);
            MyVector.removeElementAt(i);
            MyVector.add(i, MyVector.get(j));
            MyVector.removeElementAt(j);
            MyVector.add(j, temp);
        }
        
        void AddElement() throws IOException{
            System.out.println("Enter your value->");
            BufferedReader is = new BufferedReader(new InputStreamReader(System.in));
            int is1 = Integer.valueOf(is.readLine());
            ob.add(is1);
            size++;
            System.out.println("your value was added");
            System.out.println("Unsorted list");
            for(int i=0;i<size;i++){
                System.out.print(ob.get(i)+ "\t");
            }
        }
    public static void main(String[] args) throws IOException{
        Quick1 MyVec=new Quick1();//создаем обьект
        MyVec.menu();//вызываем меню на обьект
    }
}

@_Studentka_ · 21.11.2009, 16:54 **[ТС]**

Спасибо большое за код. Сейчас попробую в нем разобраться.

Но мне так интересно что же у меня за ошибка в коде и почему он не работает. Вроде все просто и логика прослеживается, но вот не получается.(( Одну ошибку я уже нашла

Java
1
2
3
4
5
6
7
8
9
10
11
12
while (i < j) {
            
            while (i < j) {
            int a = ob.get(i);
            int b = ob.get(cur);
            int c = ob.get(j);
            while (i < cur && a <= b) {
                i++;
            }
            while (j > cur && b <= c) {
                j--;
            }

Правильно было бы написать вот так:

Java
1
2
3
4
5
6
7
8
while (i < j) {
           
            while (i < cur && ob.get(i) <= ob.get(cur)) {
                i++;
            }
            while (j > cur && ob.get(cur); <= ob.get(j)) {
                j--;
            }

Раньше у меня получалось неправильно, потому что циклы работали в пустую. Ведь в цикле увеличивается значение i на 1. Значит нужно брать следующие значение, а у меня бралось одно и тоже. Потому что я поставила в цикле условие a <= b. Просто я написала уже 2 сортировки и пишу эту третью и мне хочется,чтобы в коде было меньше строк кода. Хочу сделать как-то попроще,а вот у меня не получается. И правда очень интересно почему у меня не работает.
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException : Array index out of range: 2
at java.util.Vector.get(Vector.java:694)
at quicksort.Quick1.doSort(Quick1.java:97)
at quicksort.Quick1.quickSort(Quick1.java:7 7)
at quicksort.Quick1.menu(Quick1.java:48)
at quicksort.Main.main(Main.java:22)
Java Result: 1
Вот такая вот ошибка получается((

А что это за код в несколько функций?? Очень интересно)

Добавлено через 1 минуту
Я нашла еще одну ошибку у себя и мой код заработал!!)))Разобралась я)

@lifestyle · 21.11.2009, 19:00

поздравляю а ошибка Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException : Array index out of range: 2 переполнение массива=)
все правильно заработало???
и так:
1. Функция quicSort1 как конверт получает только веткор и перенаправляет этот вектор со значениями мин и макс индекса для красоты и удобства только ради этого.
2.quick_sort разбивает рекурсивно на части массив.
3. partition сортирует части.
4. swap тривиально можно было в коде писать функции partiton но я люблю отдельно чтоб была просот меняет местами значения определенного индекса в массиве.

и все же в след раз не стоит создавать обьект, потому что ,большинство ошибок у вас были изза этого.нету прсто смысла в таком обьекте ИМХО ,и все запутанно, а если просто написать класс с функцией сортировки -то это намного проще,удобнее и понятнее было бы...

Новые блоги и статьи Все статьи Все блоги /
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .

@lifestyle Mobile Developer 238 / 234 / 18 Регистрация: 10.05.2009 Сообщений: 917
	21.11.2009, 19:00
	поздравляю а ошибка Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException : Array index out of range: 2 переполнение массива=) все правильно заработало??? и так: 1. Функция quicSort1 как конверт получает только веткор и перенаправляет этот вектор со значениями мин и макс индекса для красоты и удобства только ради этого. 2.quick_sort разбивает рекурсивно на части массив. 3. partition сортирует части. 4. swap тривиально можно было в коде писать функции partiton но я люблю отдельно чтоб была просот меняет местами значения определенного индекса в массиве. и все же в след раз не стоит создавать обьект, потому что ,большинство ошибок у вас были изза этого.нету прсто смысла в таком обьекте ИМХО ,и все запутанно, а если просто написать класс с функцией сортировки -то это намного проще,удобнее и понятнее было бы... 1