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

[_Studentka_]

Помогите,пожалуйста. Вот разбираю код :

template <class T>
void QuickSort(T A[], int low, int high)
{
  // локальные переменные, содержащие индекс середины - mid,
  // центральный элемент и индексы сканирования
  T pivot;
  int scanUp, scanDown;
  int mid;

  // если диапазон индексов не включает в себя
  // как минимум два элемента, завершить работу
  if(high - low <= 0)
    return;
  else if(high - low == 1)
  {
    // если в подсписке два элемента, сравнить их между собой
    // и поменять местами при необходимости
    if(A[high] < A[low])
      Swap(A[low], A[high]);
    return;
  }

И я не понимаю куда и что мы возвращаем,используя return. Объясните,если знаете.

[netrino]

Мы никуда и ничего не возвращаем, мы просто выходим из функции. Во всех void-функциях return можно опустить, но он тем не менее неявно присутствует. Указывая его явно мы также можем определить точку выхода из функции

[ОДИНОЧЕСТВО В СЕТИ]

Оператор return

завершает выполнение функции, в которой он задан, и возвращает управление в вызывающую функцию, в точку, непосредственно следующую за вызовом.

[_Studentka_]

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

Мы никуда и ничего не возвращаем, мы просто выходим из функции. Во всех void-функциях return можно опустить, но он тем не менее неявно присутствует. Указывая его явно мы также можем определить точку выхода из функции

Спасибо большое, я поняла. Объяснение очень хорошее))

Вот пишу сортировку и возник еще один вопрос. Вот счетчик low проходит снизу до средины массива, а счетчик high в программе проходит от конца массbва к средине. Это два индекса.
А вот в цикле

 if(high - low <= 0)
    return;

я должна как-то инициализировать значение high и low?. Просто нашла код в интернете,но там нет этой инициализации. А я вот считаю,что нужно указать,что low начинает считать с нуля (тоесть low = 0), а вот high = size.

[Greblin]

У Вас же low и high - это параметры функции, при вызове и задаёте

[_Studentka_]

Спасибо. Задала уже значение индексам)

Вот еще один вопрос((
У меня метод содержит два параметра:

void QuickSort(int low,int size)

Я вызываю эту функцию в этом же классе. Вот так вот QuickSort(a1, b1);
а1 и b1 определила раньше в этом же классе. (int a1,b1) Просто компилятор не ругается. Но у меня возникают ошибки при выполнении. Я вот думаю,что именно при вызове этой функции с параметрами у меня возможна ошибка. Подскажите,пожалуйста,могу ли я делать так,как я сделала??

[netrino]

Было бы лучше, если бы Вы предоставили весь код, так сложно понять
Возможно a1 и b1 имеют неправильные значения? Например не были инициализированы к моменту вызова функции QuickSort?

[_Studentka_]

Код у меня очень длинный и делала я его на векторных списках(((

package quicksort;

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 low,high, ScanUp,ScanDown,t,el1,el2,temp,pivot,mid,n,m,k,s,size,a1,b1;
    Quick1(){
        low=0;

        ScanUp=0;
        ScanDown=0;
        t=0;
        n=0;
        m=0;
        k=0;
        s=0;
        temp=0;
        size=0;
        low=0;
        a1=0;
        b1=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(a1, b1);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++;
     low=0;
 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 Swap(int el1,int el2,int l, int s){

   temp=el1;
   ob.set(l, el2);
   ob.set(s, temp);

}

    void QuickSort(int low,int size){

            int a=ob.get(low);
            int b= ob.get(size);
            if(size-low<=0)
            return;
            else if(size-low==1){
            if(ob.get(size)<ob.get(low))


            Swap(a,b,low,size);
            return;
    }

        mid = (low+size)/2;
        pivot = ob.get(mid);
        Swap(pivot,a,mid,low);
        ScanUp = low+1;
        ScanDown = size;
        while(ScanUp<ScanDown){
            while(ScanUp<=ScanDown && ob.get(ScanUp)<=pivot)
                ScanUp++;
            while(ob.get(ScanDown)>pivot)
                ScanDown--;
            if(ScanUp<ScanDown){
                int d = ob.get(ScanUp);
                int e = ob.get(ScanDown);
                Swap(d,e,ScanUp,ScanDown);
            }
            }
        int f = ob.get(ScanDown);
        ob.set(low,f);
        ob.set(ScanDown,pivot);
        if(low<ScanDown-1){
            QuickSort(low,ScanDown-1);
            if(ScanDown+1<size)
                QuickSort(ScanDown+1,size);

        }
        System.out.println("Sorted List:");
        for(int i=0;i<size;i++){
            System.out.println(ob.get(i)+"\t");
        }

}

}

Вот получается ошибка выполнения. ((Думаю,что при вызове функции быстрой сортировки что-то не так работает!!

[netrino]

Оу, Java... Честно говоря не сталкивался с ней
Тем не менее, из того, что как мне кажется может быть важным, я бы отметил отсутствие инициализации ob. Где-то в конструкторе наверное надо добавить нечто вроде ob = new Vector<Integer>;, может поможет

[_Studentka_]

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

Оу, Java... Честно говоря не сталкивался с ней
Тем не менее, из того, что как мне кажется может быть важным, я бы отметил отсутствие инициализации ob. Где-то в конструкторе наверное надо добавить нечто вроде ob = new Vector<Integer>;, может поможет

Спасибо еще раз))) Сейчас попробую))