[Java] Сортировка пузырьком « Записки программиста

15Сен/126

[Java] Сортировка пузырьком

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

Что такое сортировка пузырьком?
Это когда последовательно берется каждый элемент массива и "всплывается" на своё место пока не встретит более "легкий" элемент или конец массива.

Что для этого надо?
Для начала, нужно проходить по всему массиву:

for(int i = 0; i < arr.length; i++)

Ничего сложного, да?
Теперь надо каждый найденный элемент поднимать вверх.

for(int i = 1; i < arr.length; i++)	//внимание на начальный номер
					//связано это с тем, что сравниваем с "предыдущим" пузырьком
					//но индекса "-1" в массиве нет
{
	for(int j = i; j >= 1; j--)
	{
		//меняем элементы местами
		int a = arr[j];
		arr[j] = arr[j-1];
		arr[j-1] = a;
	}
}

Элементы "всплывают". Но чего-то не хватает... Точно, проверки - нужно ли вообще всплывать!

for(int i = 1; i < arr.length; i++)
{
	for(int j = i; (j >= 1) && (arr[j] < arr[j - 1]); j--)
	//ПОКА (arr[j] меньше arr[j-1]) И (в массиве еще есть элементы (j >= 0))
        {
                int a = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = a;
	}
}

Вот так вот.
Массив для проверки можно создать так:

int arr[] = {4, 7, 2, 9, 0, 1, 9, 12 ,56 ,78};

Но мы жешь программисты!
Так что воспользуемся готовой функцией random!

int arr[] = new inr[10];
for(int i = 0; i < arr.length; i++)
	arr[i] = Math.random();

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

Метки записи: Example, Java, Сортировка Оставить комментарий

Комментарии (6) Пинги (0) (подписаться на новые комментарии в этой ветке)

Lada
Сентябрь 20th, 2012 - 08:41

1. Массивы целых чисел не получается сделать рандомом.
2. Гном через while не получается. Как в этой среде сделать пошаговую работу, чтоб он показывал — сейчас я делаю это?
3. Count++ — какое у этой конструкции назначение? У меня она не работает.
Утро кончилось.

Пузырёк

public class hello
{
public static void main (String[] args)
{
double mas[];
mas=new double[20];
for (int i=0; i<mas.length; i++)
{
mas[i]= Math.floor(Math.random()*100);
System.out.println(mas[i]+" "); //пробел еще под вопросом, потому что результат записывается в этом случае в столбик
}
System.out.println();
for (int i=1;i=1)&&(mas[j]<mas[j-1]); j—)
{
//count ++;
double a=mas[j];
mas[j]=mas[j-1];
mas[j-1]=a;
}
}
for (int i=0; i<mas.length; i++)
{
System.out.println(mas[i]+" ");
}
System.out.println();
}
}

Убывание (разница в одном символе)

public class hello
{
public static void main (String[] args)
{
double mas[];
mas=new double[20];
for (int i=0; i<mas.length; i++)
{
mas[i]= Math.floor(Math.random()*100);//((Math.random(1 to 100)*100)%1);
System.out.println(mas[i]+" ");
}
System.out.println();
for (int i=1;i=1)&&(mas[j]>mas[j-1]); j—)
{
//count ++;
double a=mas[j];
mas[j]=mas[j-1];
mas[j-1]=a;
}
}
for (int i=0; i<mas.length; i++)
{
System.out.println(mas[i]+" ");
}
System.out.println();
}
}

Гном

public class hello
{
public static void main (String[] args)
{
double mas[];
mas=new double[10];
for (int i=0; i<mas.length; i++)
{
mas[i]= Math.floor(Math.random()*100);//((Math.random(1 to 100)*100)%1);
System.out.println(mas[i]+" ");
}
System.out.println();

//гном
for (int i=1; i<mas.length;)
{
if ( mas[i-1]<= mas[i] )
{
i++;
}
else
{
double a=mas[i];
mas[i]=mas[i-1];
mas[i-1]=a;
i—;
if (i==0 )
{
i=1;
}
}
}

for (int i=0; i<mas.length; i++)
{
System.out.println(mas[i]+" ");
}
System.out.println();
}
}

( REPLY )
- Axis
  Сентябрь 24th, 2012 - 14:02
  
  > 1. Массивы целых чисел не получается сделать рандомом.
  
  Надо привести тип возвращаемого рандомом значения к целому числу:
  mas[i]= (int)(Math.random()*100);
  
  > 2. Гном через while не получается. Как в этой среде сделать пошаговую работу, чтоб он показывал – сейчас я делаю это?
  
  Гном у тебя получился неправильным. Он не возвращается на позицию, с которой начал менять элемент.
  Для отладки надо сначала поставить бряк на строчку, где ты хочешь начать отладку. Ставится он путем клика в сером поле слева от нужной строчки. Ну, а потом надо нажать не Run, а Debug.
  
  > 3. Count++ – какое у этой конструкции назначение? У меня она не работает.
  
  Оно лишнее. Убрал.
  
  ( REPLY )
- Axis
  Сентябрь 24th, 2012 - 14:06
  
  У System.out есть две функции вывода.
  print() — просто выводит строчку.
  println() — выводит строку и делает переход на следующую.
  
  ( REPLY )
Andrey
Май 25th, 2017 - 10:14

Собака программиста на F# очень похожа на собаку кодера OCaml с той лишь разницей, что выходит гулять из дома только через окно.

( REPLY )
- Axis
  Июнь 22nd, 2017 - 16:44
  
  К чему бы это? :)
  
  ( REPLY )
Dmitry
Июнь 7th, 2018 - 09:52

Пузырек!

public class BubbleSort {
public int[] Sort(int[] array) {
int j = 0;
int CounterPairs = 0;
while (true) {
if (array[j] > array[j + 1]) {
int q = array[j];
array[j] = array[j + 1];
array[j + 1] = q;
CounterPairs = 0;
} else {
CounterPairs++;
}
j++;
if (j == array.length — 1) {
j = 0;
}
if (CounterPairs == array.length — 1)
break;
}
return array;
}
}

// @Test
import org.junit.Test;
import static org.hamcrest.Matchers.is;
import static org.junit.Assert.assertThat;

public class BubbleSortTest {
@Test
public void whenEnterEvenArrayThenSortArray() {
BubbleSort sorter = new BubbleSort();
int[] input = new int[] {11, -2, -7, 0, 10, 1};
int[] result = sorter.Sort(input);
int[] expect = new int[] {-7, -2, 0, 1, 10, 11};
assertThat(result, is(expect));
}

@Test
public void whenEnterOddArrayThenSortArray() {
BubbleSort sorter = new BubbleSort();
int[] input = new int[] {2, 1, 5, 4, 3};
int[] result = sorter.Sort(input);
int[] expect = new int[] {1, 2, 3, 4, 5};
assertThat(result, is(expect));
}
}

( REPLY )

Записки программиста Программирование и не только

[Java] Сортировка пузырьком

Leave a comment Отменить ответ

Рубрики

Архивы

Мета

Метки