Definisi dan Cara Penggunaan Quick Sort

Quick Sort

Quick Sort adalah algoritma sort yang tercepat dari antara sort-sort O(N log N) lainnya. Tetapi, Quick Sort juga algoritma yang running timenya tidak stabil. Artinya, dijamin 99,9999% bahwa Quick Sort akan berjalan dengan sangat cepat, tetapi pada kasus-kasus tertentu Quick Sort akan berjalan agak lambat, dan kalau sedang sial, untuk input tertentu (worst case) Quick Sort akan berjalan dengan waktu O(N²). Tapi pada umumnya (average case), Quick Sort berjalan dengan waktu O(N log N). Algoritma ini sangat unik. Inti dari algoritma ini:

procedure Quicksort(a, b: integer);

var

    pivot: integer;

begin

    if (b > a) then

    begin

        pivot := A[(a + b) div 2];

        pindahkan semua elemen yang lebih kecil dari pivot ke sebelah kiri pivot

        pindahkan semua elemen yang lebih besar dari pivot ke sebelah kanan pivot

        misalkan pivot akhirnya berada di posisi j, maka

            Quicksort(a, j - 1);

            Quicksort(j + 1, b);

    end;

end;

dengan pemanggilan pertama

    Quicksort(1, N);

Basis dari prosedur rekursif ini adalah pada kasus b <= a, yaitu ketika hanya ada maksimum 1 elemen yang akan disort. Pivot dapat dipilih secara acak, dan bisa elemen apapun dari antara A[a..b]. Untuk kasus di atas, kita pilih elemen ke-(a + b) div 2.

Di bawah ini adalah ilustrasi Quick Sort, di mana elemen yang diberi kotak biru adalah pivot. Perhatikan bahwa elemen-elemen yang lebih kecil dari pivot diletakkan di sebelah kiri pivot, dan yang lebih besar di sebelah kanan pivot.

Salah satu implementasi Quick Sort dapat dilihat pada contoh berikut:

procedure Quicksort(a, b: integer);

var

    pivot: integer;

    left, right: integer;

begin

    if (b > a) then

    begin

        pivot := A[(a + b) div 2];

        left := a;  right := b;

        while (left <= right)

        begin

            while (A[left] < pivot)  left := left + 1;

            while (A[right] > pivot) right := right - 1;

            if (left <= right) then

            begin

                swap A[left] dengan A[right]

                left := left + 1;

                right := right - 1;

            end;

        end;

        // sampai di sini, tentu left > right

        Quicksort(a, right);

        Quicksort(left, b);

    end;

end;

Algoritma sort yang stabil

Kadang kala input yang kita miliki dapat memiliki elemen-elemen bernilai sama seperti

1 2 3 1 3 1 2 2

sehingga jika diurutkan dari kecil ke besar menjadi

1 1 1 2 2 2 3 3

Pada kasus ini tidak ada masalah, karena angka-angka yang sama tidak bisa dibedakan. Namun bagaimana jika Anda diberikan input

makan

lomba

main

tidur

toki

lalu Anda harus mengurutkan kata-kata tersebut dari yang pendek ke panjang? Bagaimana memecahkan kondisi seri (tie) antara "toki" dan "main", dan juga antara "makan", "lomba", dan "tidur"? Algoritma sort yang stabil (stable) adalah algoritma yang dapat mengurutkan input, dan jika menemukan kondisi seri, akan mengeluarkan elemen-elemen yang seri sesuai dengan urutan input awal. Pada contoh di atas, algoritma yang stabil akan mengeluarkan:

main

toki

makan

lomba

tidur

karena "main" muncul terlebih dahulu daripada "toki", dan "makan" muncul dahulu daripada "lomba", lalu daripada "tidur".

Dari algoritma-algoritma yang sudah kita pelajari di atas, semua algoritma stabil kecuali Quick Sort. Ketika menggunakan Quick Sort, kita tidak bisa menentukan urutan relatif dari elemen-elemen yang seri.

Berikut ini adalah tabel perbandingan algoritma-algoritma sort yang sudah kita pelajari:

Algoritma	Stabil	Running time	Catatan
Selection Sort	Ya	O(N2)	Running time tidak tergantung input
Insertion Sort	Ya	O(N2)	Jika input hampir terurut, running time menjadi sangat cepat
Bubble Sort	Ya	O(N2)	Lambat dibandingkan algoritma O(N2) lainnya
Merge Sort	Ya	O(N log N)	Running time tidak tergantung input
Quick Sort	Tidak	O(N log N)	Paling cepat dibandingkan algoritma O(N log N) lainnya, tetapi pada kasus terburuk (sangat jarang terjadi) menjadi O(N2). Algoritma ini adalah algoritma yang paling populer digunakan di kompetisi informatika.

Yuki Murata -Films-

Yuki Murata (村田有希) is a pianist, composer and sound programmer in Saitama, Japan, generally known for her work in the neoclassical/post-rock band, Anoice. She has been learning various styles of piano since her childhood, and has taken many prizes in a lot of piano contests by present. However, you will be able to listen to her peculiar, beautiful and warm piano sound on her two improvisational albums “Films” and “Home”

.Download

 Download

Noveller -Glacial Glow-

Noveller is the solo project of Brooklyn-based sound artist and filmmaker [ Sarah Lipstate ]. She has performed in [ Rhys Chatham’s ] Guitar Army, and as a member of [ Glenn Branca’s ] 100 guitar ensemble. In March 2008, Lipstate joined Brooklyn art-rock outfit Parts & Labor as their guitarist. She contributed to the band’s critically-acclaimed release Receivers and completed several U.S. and European tours before leaving the band in July 2009.

Last year [ Lipstate ] performed as part of the Underground at the Abrons performance series at the Abrons Arts Center on the Lower East Side of Manhattan. In December, she played at the Un Son Par Là, Music of Today festival in Nîmes, France. She recently performed in the revival of [ Rhys Chatham ] and [ Karole Armitage’s ] ” Drastic-Classicism ” as part of the Think Punk! program at The Kitchen in NYC.

Following that performance, she joined [ Rhys Chatham ] and his cast of guitar-allstars at the Metropolitan Museum of Art for a performance of his minimalist punk classic ” Guitar Trio “. Along with 199 other guitar players, Lipstate performed in Chatham’s ” A Crimson Grail ” for 200 guitars which debuted at Lincoln Center’s Damrosch Park in August 2009.

In April, No Fun Productions released her debut LP Paint on the Shadows. Following the release, Lipstate performed at No Fun Fest at the Music Hall of Williamsburg in Brooklyn. In September, the label released her full-length CD follow-up titled Red Rainbows and Lipstate performed at No Fun Fest Sweden in Stockholm.

Her short films screened at the SXSW film festival in both 2006 and 2007, and earned Lipstate the ” Diamond in the Rough Cut ” award for exceptional emerging filmmaker at Cinematexas 2006. Her short, Memory Scars, screened at the Reel Venus Film Festival at Anthology Film Archives in NYC in October 2008. She debuted a new short film, Interior Variations, at the New Museum in NYC as part of No Fun: Infinite Sound and Image in May.

She has previously performed as a member of Cold Cave, Parts & Labor, One Umbrella and Sands. Lipstate received a BS in Radio-Television-Film at the University of Texas at Austin in December 2006, and currently resides in the Bushwick neighborhood of Brooklyn, NY.

Download

Water Fai -Girls In The White Dream-

 

Water Fai are a Japanese psychedelic-pop band, formed in Osaka in 2002. These four women dynamically contrast intricate melodies and soft harmonies with violent guitar-noise and electronic effects. They bring a much needed feminine approach to the post-rock genre that is so often dominated by male artists (and their biggest influences) like Mogwai and Tortoise. They bring their own translation of the sentimentality captured best by The Album Leaf and Yo La Tengo.

  

Download 

 

Nils Frahm -Wintermusik-

Nils Frahm, born in 1982, had an early introduction to music. During his childhood he was taught to play piano by Nahum Brodski – a student of the last scholar of Tschaikowski. It was through this that Nils began to immerse himself in the styles of the classical pianists before him as well as contemporary composers. Today Nils Frahm works as a composer and producer in Berlin. In early 2008 he founded Durton Studio, where he has worked with likeminded musicians.

The three instrumentals, which make up his debut release 'Wintermusik' are piano led pieces, coloured with occasional celeste and reed organ parts. The record’s equal measures of sorrowful refrains and uplifting passages, combined with a real intimacy that makes for an album you'll want to return to again and again. The songs were originally intended as a Christmas present for friends and family and first released on sonic pieces, hence its winter release via London-based cinematic music label Erased Tapes.
30 minutes of piano, celeste and reed organ recorded by Nils Frahm at Durton Studio on the 21st and 22nd of December 2007.

download 

Jonsi - Go Live/Go Quiet (Film)

I dont have any words to describe this film. Just download it and watch this amazing film!!!




Download

http://hotfile.com/dl/89174993/77305b1/J-GL(MP4).part1.rar.html  http://hotfile.com/dl/89176370/b7785fb/J-GL(MP4).part2.rar.html  http://hotfile.com/dl/89177359/471b7da/J-GL(MP4).part3.rar.html

New Japanese signing on U-cover and the last release of 2007! Shunichiro Fujimoto from Tokyo has a solo project called fjordne. Here he processes only acoustic instruments such as piano and guitars into some exciting, experimental minded ambient, resulting in something that comes between the typical Fennesz and Oval sound but still with his own original sign. Unmoving is another well made debut from an artist from whom we will hear a lot more soon.




The Setting Sun

Download