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

01.10.2011, 00:30. **Показов** 1415. **Ответов** 1

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

Доброй ночи! ))
разбираюсь в java.
написал алгоритм быстрой сортировки, и не могу понять в чем ошибка... вроде не первый день программирую

работает, но корявенько.
Помогите, плиз! )))
Короче,
Metrics() - класс который только хранит 3 переменных кол-ва обменов, сравнений и запусков рекурсии

Java

public class Sort {
    public int[] values;
    public Metrics mt=new Metrics();    
        public void swap(int i, int j) {
        mt.swapCount++;
        
        int temp=values[i];
        values[i]=values[j];
        values[j]=temp;
        
        for (int x = 0; x < values.length; x++) {
            System.out.print(values[x] + " ");
        }
        System.out.println("");
        
    }
 
    public int compare(int i, int j) {
        mt.compareCount++;
        if (values[i]==values[j]) {
            return 0;
        } else {
            if (values[i]>values[j]) {
                return -1;
            } else return 1;
        }
    }
 
public class RecSort extends Sort {
    public void recSort(int left,int right){
            
        int i = left;
        int j = right;
        int x=Math.round((j-i) / 2)+i;
        do {
            while (compare (i,x)==1) {i++;}
            while (compare (x,j)==1) {j--;}
            if (i<=j) {
                swap(i++,j--);          
            }
//          if (i==j) {
//              i++;
//              j--;
//          }
        } while (i<=j);
        if (left<j) {
            recSort(left,j);
        }
        if (i<right) {
            recSort(i,right);
        }
        
                
    }
    public int[] doSort(int[] data){
        mt.init();
        values = data;      
        recSort(0,data.length-1);
 
        System.out.println(mt.toString());
        
        return values;
    }
 
}

результат работы программы:
Рекурсивная сортировка:
7 55 6 48 2 10 100 55 18 -5 5 3 15 48 1589 786 13 1 8 8 18 24 489 26986 12 -59832 21 37 5 4 1 999 27 3
7 3 6 48 2 10 100 55 18 -5 5 3 15 48 1589 786 13 1 8 8 18 24 489 26986 12 -59832 21 37 5 4 1 999 27 55
7 3 6 1 2 10 100 55 18 -5 5 3 15 48 1589 786 13 1 8 8 18 24 489 26986 12 -59832 21 37 5 4 48 999 27 55
7 3 6 1 2 10 4 55 18 -5 5 3 15 48 1589 786 13 1 8 8 18 24 489 26986 12 -59832 21 37 5 100 48 999 27 55
7 3 6 1 2 10 4 5 18 -5 5 3 15 48 1589 786 13 1 8 8 18 24 489 26986 12 -59832 21 37 55 100 48 999 27 55
7 3 6 1 2 10 4 5 -59832 -5 5 3 15 48 1589 786 13 1 8 8 18 24 489 26986 12 18 21 37 55 100 48 999 27 55
7 3 6 1 2 10 4 5 -59832 -5 5 3 12 48 1589 786 13 1 8 8 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
7 3 6 1 2 10 4 5 -59832 -5 5 3 12 8 1589 786 13 1 8 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
7 3 6 1 2 10 4 5 -59832 -5 5 3 12 8 8 786 13 1 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
7 3 6 1 2 10 4 5 -59832 -5 5 3 12 8 8 1 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 3 6 1 2 10 4 5 7 -5 5 3 12 8 8 1 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 3 6 1 2 5 4 10 7 -5 5 3 12 8 8 1 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 1 6 3 2 5 4 10 7 -5 5 3 12 8 8 1 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 1 6 2 3 5 4 10 7 -5 5 3 12 8 8 1 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 10 7 -5 5 3 12 8 8 1 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 1 7 -5 5 3 12 8 8 10 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 1 3 -5 5 7 12 8 8 10 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 1 -5 3 5 7 12 8 8 10 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 -5 1 3 5 7 12 8 8 10 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 12 10 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 12 10 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 786 1589 48 18 24 489 26986 15 18 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 18 1589 48 18 24 489 26986 15 786 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 18 15 48 18 24 489 26986 1589 786 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 18 15 24 18 48 489 26986 1589 786 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 15 18 24 18 48 489 26986 1589 786 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 15 18 18 24 48 489 26986 1589 786 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 15 18 18 24 48 489 26986 1589 786 21 37 55 100 48 999 27 55
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 15 18 18 24 48 489 55 1589 786 21 37 55 100 48 999 27 26986
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 15 18 18 24 48 489 55 27 786 21 37 55 100 48 999 1589 26986
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 15 18 18 24 48 489 55 27 48 21 37 55 100 786 999 1589 26986
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 15 18 18 24 48 489 37 27 48 21 55 55 100 786 999 1589 26986
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 15 18 18 24 48 489 37 27 21 48 55 55 100 786 999 1589 26986
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 15 18 18 24 48 489 21 27 37 48 55 55 100 786 999 1589 26986
-59832 1 6 2 3 4 5 -5 1 3 5 7 8 8 10 12 13 15 18 18 24 48 489 21 27 37 48 55 55 100 786 999 1589 26986

в момент когда i и j сходятся на одном значении и выполняется замена одного и того же элемента - происходит i++ и j-- после чего 1 элемент остается не у дел

Вначале думал, что подзабыл стандартный алгоритм... а нет - википедия предлагает тот же самый вариант... только с другими переменными....
короче, запарился искать ошибку)

Добавлено через 12 минут
как сдесь удалить тему?

2-й раз пощу сдесь просьбу о помощи.... и через 3 минуты после того как запостил - нахожу ошибку в своей программке

Мне нравится этот форум!

а бился над проблеммой ооочень долго

@Gerbasha · 23.10.2011, 23:36

А зачем тему удалять? ) добавь с исправленной ошибкой) в друг у других возникнит похожая проблема ?

@Gerbasha 6 / 6 / 2 Регистрация: 04.10.2011 Сообщений: 115
	23.10.2011, 23:36	2
	А зачем тему удалять? ) добавь с исправленной ошибкой) в друг у других возникнит похожая проблема ? 0